Approximation hardness of dominating set problems in bounded degree graphs

Janka Chlebikova; M. Chlebik

doi:10.1016/j.ic.2008.07.003

Approximation hardness of dominating set problems in bounded degree graphs

Janka Chlebikova, M. Chlebik

School of Computing

Research output: Contribution to journal › Article › peer-review

264 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 language	English
Pages (from-to)	1264-1275
Number of pages	12
Journal	Information and Computation
Volume	206
Issue number	11
DOIs	https://doi.org/10.1016/j.ic.2008.07.003
Publication status	Published - Nov 2008

Keywords

dominatig set problems
bounded-degree graphs
approximation hardness

Access to Document

10.1016/j.ic.2008.07.003

DOMINATING_elsart.pdf

http://portal.acm.org/citation.cfm?id=1453257.1453393&coll=DL&dl=GUIDE&CFID=29403851&CFTOKEN=59301073

Cite this

@article{a4f3b74e03f64180a8978cf0dd00a505,

title = "Approximation hardness of dominating set problems in bounded degree graphs",

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.",

keywords = "dominatig set problems, bounded-degree graphs, approximation hardness",

author = "Janka Chlebikova and M. Chlebik",

note = "Funders: VEGA grant no. 1/3106/06 (Slovakia).",

year = "2008",

month = nov,

doi = "10.1016/j.ic.2008.07.003",

language = "English",

volume = "206",

pages = "1264--1275",

journal = "Information and Computation",

number = "11",

}

TY - JOUR

T1 - Approximation hardness of dominating set problems in bounded degree graphs

AU - Chlebikova, Janka

AU - Chlebik, M.

N1 - Funders: VEGA grant no. 1/3106/06 (Slovakia).

PY - 2008/11

Y1 - 2008/11

N2 - 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.

AB - 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.

KW - dominatig set problems

KW - bounded-degree graphs

KW - approximation hardness

U2 - 10.1016/j.ic.2008.07.003

DO - 10.1016/j.ic.2008.07.003

M3 - Article

VL - 206

SP - 1264

EP - 1275

JO - Information and Computation

JF - Information and Computation

IS - 11

ER -

Approximation hardness of dominating set problems in bounded degree graphs

Abstract

Keywords

Access to Document

Fingerprint

Cite this