Approximation hardness of dominating set problems in bounded degree graphs

Janka Chlebikova, M. Chlebik

Research output: Contribution to journalArticlepeer-review

191 Downloads (Pure)

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.
Original languageEnglish
Pages (from-to)1264-1275
Number of pages12
JournalInformation and Computation
Volume206
Issue number11
DOIs
Publication statusPublished - Nov 2008

Keywords

  • dominatig set problems
  • bounded-degree graphs
  • approximation hardness

Fingerprint

Dive into the research topics of 'Approximation hardness of dominating set problems in bounded degree graphs'. Together they form a unique fingerprint.

Cite this