Fixed-parameter tractable algorithms for Tracking Shortest Paths

• Published in: Theoretical computer science 2020-12, Vol.846, p.1-13
• Main Authors: Banik, Aritra, Choudhary, Pratibha, Raman, Venkatesh, Saurabh, Saket
• Format: Article
• Language: English
• Subjects: Fixed-parameter tractable; Graphs; Kernel; Set systems; Shortest s-t paths; Tracking paths
• ISSN: 0304-3975; 1879-2294
• DOI: 10.1016/j.tcs.2020.09.006

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 in solving Tracking Shortest Paths when the input graph diameter is bounded by d. While the results for Tracking Set System 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.