Center for Algorithms and Theory of Computation

CS 269S, Fall 2018: Theory Seminar
Bren Hall, Room 1423, 1pm

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.)