Polynomial Time Algorithms for Tracking Path Problems

Given a graph G, and terminal vertices s and t, the Tracking Paths problem asks to compute a minimum number of vertices to be marked as trackers, such that the sequence of trackers encountered in each s-t path is unique. Tracking Paths is NP-hard in both directed and undirected graphs in general. In this paper we give a collection of polynomial time algorithms for some restricted versions of Tracking Paths. We prove that Tracking Paths is polynomial time solvable for chordal graphs and tournament graphs. We prove that Tracking Paths is NP-hard in graphs with bounded maximum degree d = 6, and give a 2(d + 1)-approximate algorithm for the same. We also analyze the version of tracking s-t paths where paths are tracked using edges instead of vertices, and we give a polynomial time algorithm for the same. Finally we give a polynomial algorithm which, given an undirected graph G, a tracking set T ? V (G), and a sequence of trackers p, returns the unique s-t path in G that corresponds to p, if one exists.