Parameterized and approximation complexity of the detection pair problem in graphs

Florent Foucaud, Ralf Klasing

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…