  We consider the parameterized complexity of the problem of tracking shortest
s-t paths in graphs, motivated by applications in security and wireless
networks. Given an undirected and unweighted graph with a source s and a
destination t, Tracking Shortest Paths asks if there exists a k-sized subset of
vertices (referred to as tracking set) that intersects each shortest s-t path
in a distinct set of vertices. We first generalize this problem for set
systems, namely Tracking Set System, where given a family of subsets of a
universe, we are required to find a subset of elements from the universe that
has a unique intersection with each set in the family. Tracking Set System is
shown to be fixed-parameter tractable due to its relation with a known problem,
Test Cover. By a reduction to the well-studied d-hitting set problem, we give a
polynomial (with respect to k) kernel for the case when the set sizes are
bounded by d. This also helps solving Tracking Shortest Paths when the input
graph diameter is bounded by d. While the results for Tracking Set System help
to show that Tracking Shortest Paths is fixed-parameter tractable, we also give
an independent algorithm by using some preprocessing rules, resulting in an
improved running time.
