Domination when the stars are out

Danny Hermelin; Matthias Mnich; Erik Jan van Leeuwen; Gerhard J. Woeginger

doi:10.1007/978-3-642-22006-7_39

Domination when the stars are out

Danny Hermelin, Matthias Mnich, Erik Jan van Leeuwen, Gerhard J. Woeginger

Research output: Chapter in Book/Report/Conference proceeding › Conference article in proceeding › Academic › peer-review

Abstract

We algorithmize the recent structural characterization for claw-free graphs by chudnovsky and seymour. Building on this result, we show that dominating set on claw-free graphs is (i) fixed-parameter tractable and (ii) even possesses a polynomial kernel. To complement these results, we establish that dominating set is not fixed-parameter tractable on the slightly larger class of graphs that exclude k 1,4 as an induced subgraph. Our results provide a dichotomy for dominating set in k 1,l-free graphs and show that the problem is fixed-parameter tractable if and only if l = 3. Finally, we show that our algorithmization can also be used to show that the related connected dominating set problem is fixed-parameter tractable on claw-free graphs.

Original language	English
Title of host publication	Automata, Languages and Programming
Subtitle of host publication	38th International Colloquium, ICALP 2011, Zurich, Switzerland, July 4-8, 2011, Proceedings, Part I
Publisher	Springer
Pages	462-473
DOIs	https://doi.org/10.1007/978-3-642-22006-7_39
Publication status	Published - 2011
Externally published	Yes

Publication series

Series	Lecture Notes in Computer Science
Volume	6755

Access to Document

10.1007/978-3-642-22006-7_39

Cite this

@inproceedings{9f47d2907a664e7a91d055e505e1f2f9,

title = "Domination when the stars are out",

abstract = "We algorithmize the recent structural characterization for claw-free graphs by chudnovsky and seymour. Building on this result, we show that dominating set on claw-free graphs is (i) fixed-parameter tractable and (ii) even possesses a polynomial kernel. To complement these results, we establish that dominating set is not fixed-parameter tractable on the slightly larger class of graphs that exclude k 1,4 as an induced subgraph. Our results provide a dichotomy for dominating set in k 1,l-free graphs and show that the problem is fixed-parameter tractable if and only if l = 3. Finally, we show that our algorithmization can also be used to show that the related connected dominating set problem is fixed-parameter tractable on claw-free graphs.",

author = "Danny Hermelin and Matthias Mnich and {van Leeuwen}, {Erik Jan} and Woeginger, {Gerhard J.}",

year = "2011",

doi = "10.1007/978-3-642-22006-7_39",

language = "English",

series = "Lecture Notes in Computer Science",

publisher = "Springer",

pages = "462--473",

booktitle = "Automata, Languages and Programming",

address = "United States",

}

Domination when the stars are out. / Hermelin, Danny; Mnich, Matthias; van Leeuwen, Erik Jan et al.
Automata, Languages and Programming: 38th International Colloquium, ICALP 2011, Zurich, Switzerland, July 4-8, 2011, Proceedings, Part I. Springer, 2011. p. 462-473 (Lecture Notes in Computer Science, Vol. 6755).

Research output: Chapter in Book/Report/Conference proceeding › Conference article in proceeding › Academic › peer-review

TY - GEN

T1 - Domination when the stars are out

AU - Hermelin, Danny

AU - Mnich, Matthias

AU - van Leeuwen, Erik Jan

AU - Woeginger, Gerhard J.

PY - 2011

Y1 - 2011

N2 - We algorithmize the recent structural characterization for claw-free graphs by chudnovsky and seymour. Building on this result, we show that dominating set on claw-free graphs is (i) fixed-parameter tractable and (ii) even possesses a polynomial kernel. To complement these results, we establish that dominating set is not fixed-parameter tractable on the slightly larger class of graphs that exclude k 1,4 as an induced subgraph. Our results provide a dichotomy for dominating set in k 1,l-free graphs and show that the problem is fixed-parameter tractable if and only if l = 3. Finally, we show that our algorithmization can also be used to show that the related connected dominating set problem is fixed-parameter tractable on claw-free graphs.

AB - We algorithmize the recent structural characterization for claw-free graphs by chudnovsky and seymour. Building on this result, we show that dominating set on claw-free graphs is (i) fixed-parameter tractable and (ii) even possesses a polynomial kernel. To complement these results, we establish that dominating set is not fixed-parameter tractable on the slightly larger class of graphs that exclude k 1,4 as an induced subgraph. Our results provide a dichotomy for dominating set in k 1,l-free graphs and show that the problem is fixed-parameter tractable if and only if l = 3. Finally, we show that our algorithmization can also be used to show that the related connected dominating set problem is fixed-parameter tractable on claw-free graphs.

U2 - 10.1007/978-3-642-22006-7_39

DO - 10.1007/978-3-642-22006-7_39

M3 - Conference article in proceeding

T3 - Lecture Notes in Computer Science

SP - 462

EP - 473

BT - Automata, Languages and Programming

PB - Springer

ER -