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