The Parameterized Complexity of Dominating Set and Friends Revisited for Structured Graphs

We consider variants and generalizations of the dominating set problem on special classes of graphs, specifically, graphs that are a small distance from a tractable class. Here, our focus is mainly on the problems of domination and efficient domination (a variant where we want every vertex to be dominated uniquely) and their respective generalizations to r-distance domination. We consider graphs which are at most k vertices away from the following classes: edgless graphs, cluster graphs, split graphs, and complements of bipartite graphs. For the newly introduced parameter CBDS, we show that DOMINATING SET is W[2] -hard, while in contrast, r-DS is FPT for T > 1. For this parameter, EFFICIENT DOMINATING SET turns out to be FPT as well. We generalize known results for DOMINATING SET parameterized by CVD to T-DOMINATING SET parameterized by CVD, inspired by algorithms for r-DS parameterized by VC, which is in general a larger parameter. We are also able to do this for the EFFICIENT DOMINATING SET problem. Finally, for the problem of efficient domination parameterized by the distance to split graphs, we improve the complexity of the known algorithm from O-star(1.732(k)) to O-star(1.616(k)). For the most part, our results generalize what is known in the current landscape, both in terms of obtaining algorithms for smaller parameters, as well as for the more general notion of domination itself, which is to dominate over larger distances.