Complexity and Algorithms for Semipaired Domination in Graphs

Abstract

For a graph $G=(V,E)$ with no isolated vertices, a set $D\subseteq 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 ${\gamma }_{pr2}(G)$. The \textsc{Minimum Semipaired Domination} problem is to find a semipaired dominating set of $G$ of cardinality ${\gamma }_{pr2}(G)$. In this paper, we initiate the algorithmic study of the \textsc{Minimum Semipaired Domination} problem. We show that the decision version of the \textsc{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\Delta +2)$-approximation algorithm for the \textsc{Minimum Semipaired Domination} problem, where $\Delta$ denote the maximum degree of the graph and show that the \textsc{Minimum Semipaired Domination} problem cannot be approximated within $(1-\epsilon )\ln |V|$ for any $\epsilon >0$ unless NP $\subseteq$ DTIME$(|V{|}^{O(\log \log |V|)})$.

arXiv admin note: text overlap with arXiv:1711.10891