Parameter­ized Algorithms for Variants of Dominating Set

Dominating Set asks for a small set of vertices so that every vertex is either chosen or adjacent to a chosen one. Parameterized by solution size it is W[2]-hard, so an FPT algorithm is unlikely in general, and a lot of its variants are just as hard. In my invited lectures at a workshop on domination in graphs, I look at what structure actually buys you. I consider variants like efficient domination and distance-r domination on graphs that are a few vertex deletions away from simple classes (cluster graphs and split graphs, for instance), and show how such structural parameters separate the tractable cases from the ones that stay hard.