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

Talk by Pedro Matias, Center for Algorithms and Theory of Computation, University of California (Irvine), 12 March 2021

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 talk, we address this latter issue, giving novel algorithms having approximation ratios of O(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.