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

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 s-t path results in a unique sequence. This problem is known to be NP-complete and has applications to animal migration tracking and detecting marathon course-cutting, but its approximability is largely unknown. In this paper, we address this latter issue, giving novel algorithms having approximation ratios of (1+ε), O(lg OPT) and O(lg n), for H-minor-free, general, and weighted graphs, respectively. We also give a linear kernel for H-minor-free graphs and make improvements to the quadratic kernel for general graphs.