Approximation hardness of dominating set problems in bounded degree graphs

doi:10.1016/j.ic.2008.07.003

Information and Computation

Volume 206, Issue 11, November 2008, Pages 1264-1275

https://doi.org/10.1016/j.ic.2008.07.003 Get rights and content

Under an Elsevier user license

open archive

Abstract

We study approximation hardness of the Minimum Dominating Set problem and its variants in undirected and directed graphs. Using a similar result obtained by Trevisan for Minimum Set Cover we prove the first explicit approximation lower bounds for various kinds of domination problems (connected, total, independent) in bounded degree graphs. Asymptotically, for degree bound approaching infinity, these bounds almost match the known upper bounds. The results are applied to improve the lower bounds for other related problems such as Maximum Induced Matching and Maximum Leaf Spanning Tree.

Cited by (0)

^☆: An extended abstract appeared at the Proceedings of the 12th Annual European Symposium on Algorithms, Bergen, Norway, September 14–17, 2004, LNCS, vol. 3221, Springer, pp. 192–203.

¹: The author was supported by VEGA Grant No. 1/3106/06.

Information and Computation

Approximation hardness of dominating set problems in bounded degree graphs☆

Abstract