Tracking Routes in Communication Networks

The minimum tracking set problem has been introduced in [Banik et al., CIAC 2017] for the case of a single source-destination pair.
There, the authors show that the problem is APX-hard and that it can be 2-approximated for the class of planar graphs, even though no hardness result is known for this case.
In this paper we focus on the case of multiple source-destination pairs and we present the first $\widetilde{O}(\sqrt{n})$-approximation algorithm for general graphs. Moreover, we prove that the problem remains NP-hard even for cubic planar graphs and all pairs $S \times D$, where $S$ and $D$ are the sets of sources and destinations, respectively.
Finally, for the case of a single source-destination pair, we design an (exact) FPT algorithm w.r.t. the maximum number of vertices at the same distance from the source.