Domination when the stars are out

Thursday, September 15, 2011 -
2:15pm to 4:15pm
We algorithmize the recent structural characterization for claw-free graphs by Chudnovsky and Seymour. Building on this result, we show that several domination problems are fixed-parameter tractable, and even possess polynomial-sized kernels, on claw-free graphs. To complement these results, we establish these problems are 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 $K_{1,L}$-free graphs and show that the problems are fixed-parameter tractable if and only if $L\geq 3$. The algorithms we obtain generalize and unify several earlier algorithms for problems on claw-free graphs, and turn the existential decomposition by Chudnovsky and Seymour into an efficient constructive decomposition. (Joint work with Danny Hermelin, Erik Jan van Leeuwen and Gerhard Woeginger.)
Matthias Mnich
International Computer Science Institute, Berkeley
Event Location: 
Fine Hall 314