Tight approximation bounds for dominating set on graphs of bounded arboricity

摘要

We consider the minimum dominating set problem on graphs with bounded arboricity. For graphs with arboricity a, we give an LP rounding algorithm that achieves an approximation factor of 3a and we complement this with a matching (up to constants) hardness of approximation result. (C) 2017 Elsevier B.V. All rights reserved.