Complexity and Algorithms for Semipaired Domination in Graphs
share
For a graph G=(V,E) with no isolated vertices, a set D⊆ V is called a semipaired dominating set of G if (i) D is a dominating set of G, and (ii) D can be partitioned into two element subsets such that the vertices in each two element set are at distance at most two. The minimum cardinality of a semipaired dominating set of G is called the semipaired domination number of G, and is denoted by γ_pr2(G). The Minimum Semipaired Domination problem is to find a semipaired dominating set of G of cardinality γ_pr2(G). In this paper, we initiate the algorithmic study of the Minimum Semipaired Domination problem. We show that the decision version of the Minimum Semipaired Domination problem is NP-complete for bipartite graphs and split graphs. On the positive side, we present a linear-time algorithm to compute a minimum cardinality semipaired dominating set of interval graphs and trees. We also propose a 1+(2Δ+2)-approximation algorithm for the Minimum Semipaired Domination problem, where Δ denote the maximum degree of the graph and show that the Minimum Semipaired Domination problem cannot be approximated within (1-ϵ) |V| for any ϵ > 0 unless NP ⊆ DTIME(|V|^O(|V|)).
READ FULL TEXT