Domination When the Stars Are Out

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.

(Joint work with Danny Hermelin, Erik Jan van Leeuwen and Gerhard Woeginger.)