arXiv IPL | tags:[ kernelization graph theory ]

# Polynomial Kernels for Tracking Shortest Paths

with Pratibha Choudhary, Dušan Knop, Jan Matyáš Křišťan, Ondřej Suchý, and Tomáš Valla*Tracking Shortest Paths* is a task where we want to add $k$ trackers to a directed acyclic graph so that any shortest path which goes from source to the target activates a unique combination of trackers.
In other words, there are no two paths that would activate the same set of trackers.
One can study this problem also in variant where the paths are not necessarily shortest – this is called *Tracking Paths* problem.

We showed that

- there is a $O(k^2)$ kernel for Tracking Paths on DAGs
- there is a $O(k)$ kernel for Tracking Paths on planar DAGs
- there is a $O(k^4)$ kernel for Tracking Shortest Paths on general graphs
- there is a $O(k^2)$ kernel for Tracking Shortest Paths on planar graphs