  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|)})$.
