Some complexity results on semipaired domination in graphs

Abstract

Let [Formula: see text] be a graph without any isolated vertices. A semipaired dominating set [Formula: see text] of G, is a dominating set of G, if D can be partitioned into cardinality 2 subsets such that the vertices in each of these subsets are at distance at most two from each other. The Min-Semi-PD problem is to compute a minimum cardinality semipaired dominating set of a given graph G. It is known that the decision version of the problem is NP-complete for bipartite graphs and split graphs. In this article, we resolve the complexity of the problem in two well studied graph classes, namely, AT-free graphs and planar graphs. We show that the decision version of the Min-Semi-PD problem remains NP-complete for planar graphs. On the positive side, we propose a polynomial-time exact algorithm for the Min-Semi-PD problem in AT-free graphs, but the complexity of the algorithm is quite high. So, in addition, we also give a linear-time constant factor approximation algorithm for the problem in AT-free graphs.

Keywords

• Semipaired domination
• AT-free graphs
• planar graphs
• NP-completeness
• approximation algorithm