Improved Kernels for Tracking Path Problems
share
Given a graph G, terminal vertices s and t, and an integer k, the Tracking Paths problem asks whether there exists at most k vertices, which if marked as trackers, would ensure that the sequence of trackers encountered in each s-t path is unique. The problem was first proposed by Banik et al. in <cit.>, where they gave results for some restricted versions of the problem. The problem was further studied in <cit.>, where the authors proved it to be NP-complete and fixed-parameter tractable. They obtained a kernel (i.e. an equivalent instance) with O(k^6) vertices and O(k^7) edges, in polynomial time. We improve on this by giving a quadratic kernel, i.e. O(k^2) vertices and edges. Further, we prove that if G is a d-degenerate graph then there exists a linear kernel. We also show that finding a tracking set of size at most n-k for a graph on n vertices is hard for the parameterized complexity class W[1], when parameterized by k.
READ FULL TEXT