Polynomial Kernels for Tracking Shortest Paths
share
Given an undirected graph G=(V,E), vertices s,t∈ V, and an integer k, Tracking Shortest Paths requires deciding whether there exists a set of k vertices T⊆ V such that for any two distinct shortest paths between s and t, say P_1 and P_2, we have T∩ V(P_1)≠ T∩ V(P_2). In this paper, we give the first polynomial size kernel for the problem. Specifically we show the existence of a kernel with 𝒪(k^2) vertices and edges in general graphs and a kernel with 𝒪(k) vertices and edges in planar graphs for the Tracking Paths in DAG problem. This problem admits a polynomial parameter transformation to Tracking Shortest Paths, and this implies a kernel with 𝒪(k^4) vertices and edges for Tracking Shortest Paths in general graphs and a kernel with 𝒪(k^2) vertices and edges in planar graphs. Based on the above we also give a single exponential algorithm for Tracking Shortest Paths in planar graphs.
READ FULL TEXT