Domination When the Stars Are Out
| Title | Domination When the Stars Are Out |
| Publication Type | Conference Paper |
| Year of Publication | 2011 |
| Authors | Hermelin, D., Mnich M., van Leeuwen E. J., & Woeginger G. |
| Page(s) | 432-473 |
| Other Numbers | 3176 |
| 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 K1,4 as an induced subgraph. Our results provide a dichotomy for Dominating Set in K1,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. |
| Bibliographic Notes | Proceedings of the 38th International Colloquium on Automata, Languages and Programming (ICALP 2011), pp. 432-473, Zurich, Switzerland |
| Abbreviated Authors | D. Hermelin, M. Mnich, E. J. van Leeuwen, and G. J. Woeginger |
| ICSI Research Group | Algorithms |
| ICSI Publication Type | Article in conference proceedings |