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

Abstract

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 and make improvements to the quadratic kernel for general graphs.