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+\epsilon )\), \(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.