Parameterized Complexity of Paired Domination

The Paired Domination problem is one of the well-studied variants of the classical Dominating Set problem. In a graph G on n
vertices, a dominating set D (set of vertices such that N[D] = V (G)) is called a paired dominating set of G, if G[D] has perfect matching. In the Paired Domination problem, given a graph G and a positive integer k, the task is to check whether G has a paired dominating set of size at
most k. The problem is a variant of the Dominating Set problem, and
hence inherits most of the hardness of the Dominating Set problem; however, the same cannot be said about the algorithmic results. In this paper, we study the problem from the perspective of parameterized complexity, both from solution and structural parameterization, and obtain
the following results.
1. We design an (non-trivial) exact exponential algorithm running in
time O(1.7159n).
2. It admits Strong Exponential Time Hypothesis (SETH) optimal algorithm parameterized by the treewidth (tw) of the graph G. The algorithm runs in time 4twnO(1); and unless SETH fails, there is no
algorithm running in time (4 − )
twnO(1) for any > 0.
3. We design an 4dnO(1) algorithm parameterized by the distance to cluster graphs. We complement this result by proving that the problem does not admit a polynomial kernel under this parameterization and under parameterization by vertex cover number.
4. Paired Domination admits a polynomial kernel on graphs that exclude a biclique Ki,j.
5. We also prove that one of the counting versions of Paired Domination parameterized by cliquewidth admits n2cwnO(1) time algorithm parameterized by cliquewidth (cw). However, it does not admit an FPT algorithm unless #SETH is false.