How to Catch Marathon Cheaters: New Approximation Algorithms for Tracking Paths

Michael T. Goodrich, Siddharth Gupta, Hadi Khodabandeh +1

Given an undirected graph, $G$, and vertices, $s$ and $t$ in $G$, the tracking paths problem is that of finding the smallest subset of vertices in $G$ whose intersection with any $…