## November 16, 2018:

# Tracking Paths

## Pedro Matias

We consider several problems dealing with tracking of moving objects
(e.g., vehicles) in networks. Given a graph $G=(V,E)$ and two vertices
$s,t \in V$, a set of vertices $T \subseteq V$ is a tracking set for $G$
(with respect to paths from $s$ to $t$), if one can distinguish between
any two paths from $s$ to $t$ by the order in which the vertices of $T$
appear (or do not appear) in them. We prove that the problem of finding
a minimum-cardinality tracking set with respect to shortest paths from
$s$ to $t$ is $\mathsf{NP}$-hard and even $\mathsf{APX}$-hard. On the
other hand, for the common case where $G$ is planar, we present a
$2$-approximation algorithm for this problem. We also consider the
following related problem: Given a graph $G$, two vertices $s$ and $t$,
and a set of forbidden vertices $V_F \subseteq V\setminus\{s,t\}$, find a
minimum-cardinality set of trackers $V^* \subset V$, such that a
shortest path $P$ from $s$ to $t$ passes through a forbidden vertex if
and only if it passes through a vertex of $V^∗$. We present a
polynomial-time (exact) algorithm for this problem.

(Based on a
paper by Banik, Katz, Packer, and Simakov at CIAC 2017.)