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

arXiv: https://arxiv.org/abs/2104.12337 · HTML: https://mlsanity.com/paper/2104.12337/

## Key facts

- Cited by 2 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 26 Apr 2021.

## Built on by (most cited first, 2 of 2)

- [Towards cumulative race time regression in sports: I3D ConvNet transfer learning in ultra-distance running events](https://mlsanity.com/paper/2208.11191/) (2022)
- [A Large-Scale Re-identification Analysis in Sporting Scenarios: the Betrayal of Reaching a Critical Point](https://mlsanity.com/paper/2401.00080/) (2023)

## Abstract (arXiv)

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.