2019/04/01 by Henning, Michael A., Pandey, Arti, Tripathi, Vikash
#Discrete Mathematics (cs.DM) #FOS: Computer and information sciences
paper · doi:10.48550/arxiv.1904.00964
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+ln(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-ε) ln|V| for any ε> 0 unless NP ⊆ DTIME(|V|O(loglog|V|)).