LAUSR

For a graph G = ( V , E ) with no isolated vertices, a set D ⊆ V $D\subseteq V$ is called a semipaired dominating set of G if ( i ) D is a dominating set of G , and ( i i ) 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 γ p r 2 ( G ). The Minimum Semipaired Domination problem is to find a semipaired dominating set of G of cardinality γ p r 2 ( 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 chordal graphs. On the positive side, we present a linear-time algorithm to compute a minimum cardinality semipaired dominating set of interval graphs. We also propose a 1 + ln ( 2 Δ + 2 ) $1+\ln (2{\Delta }+2)$ -approximation algorithm for the Minimum Semipaired Domination problem, where Δ denotes the maximum degree of the graph and show that the Minimum Semipaired Domination problem cannot be approximated within ( 1 − ???? ) ln | V | $(1-\epsilon ) \ln |V|$ for any ???? > 0 unless P=NP.