  We study the complexity of the problem DETECTION PAIR. A detection pair of a
graph $G$ is a pair $(W,L)$ of sets of detectors with $W\subseteq V(G)$, the
watchers, and $L\subseteq V(G)$, the listeners, such that for every pair $u,v$
of vertices that are not dominated by a watcher of $W$, there is a listener of
$L$ whose distances to $u$ and to $v$ are different. The goal is to minimize
$|W|+|L|$. This problem generalizes the two classic problems DOMINATING SET and
METRIC DIMENSION, that correspond to the restrictions $L=\emptyset$ and
$W=\emptyset$, respectively. DETECTION PAIR was recently introduced by Finbow,
Hartnell and Young [A. S. Finbow, B. L. Hartnell and J. R. Young. The
complexity of monitoring a network with both watchers and listeners.
Manuscript, 2015], who proved it to be NP-complete on trees, a surprising
result given that both DOMINATING SET and METRIC DIMENSION are known to be
linear-time solvable on trees. It follows from an existing reduction by Hartung
and Nichterlein for METRIC DIMENSION that even on bipartite subcubic graphs of
arbitrarily large girth, DETECTION PAIR is NP-hard to approximate within a
sub-logarithmic factor and W[2]-hard (when parameterized by solution size). We
show, using a reduction to SET COVER, that DETECTION PAIR is approximable
within a factor logarithmic in the number of vertices of the input graph. Our
two main results are a linear-time $2$-approximation algorithm and an FPT
algorithm for DETECTION PAIR on trees.
