Parameterized and approximation complexity of the detection pair problem in graphs

Florent Foucaud ; Ralf Klasing

Journal of Graph Algorithms and Applications, Tome 21 (2017) no. 6, pp. 1039-1056.

Résumé

We study the complexity of the problem ${\rm D{\small ETECTION}~P{\small AIR}}$. 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 ${\rm D{\small OMINATING}~S{\small ET}}$ and ${\rm M{\small ETRIC}~D{\small IMENSION}}$, that correspond to the restrictions $L=\emptyset$ and $W=\emptyset$, respectively. ${\rm D{\small ETECTION}~P{\small AIR}}$ 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. Networks, accepted), who proved it to be NP-complete on trees, a surprising result given that both ${\rm D{\small OMINATING}~S{\small ET}}$ and ${\rm M{\small ETRIC}~D{\small IMENSION}}$ are known to be linear-time solvable on trees. It follows from an existing reduction by Hartung and Nichterlein for ${\rm M{\small ETRIC}~D{\small IMENSION}}$ that even on bipartite subcubic graphs of arbitrarily large girth, ${\rm D{\small ETECTION}~P{\small AIR}}$ 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 ${\rm S{\small ET}~C{\small OVER}}$, that ${\rm D{\small ETECTION}~P{\small AIR}}$ 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 ${\rm D{\small ETECTION}~P{\small AIR}}$ on trees. Keywords: Graph theory, Detection pair, Metric dimension, Dominating set, Approximation algorithm, Parameterized complexity

Détail

DOI : 10.7155/jgaa.00449

Keywords: Graph theory, Detection pair, Metric dimension, Dominating set, Approximation algorithm, Parameterized complexity