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 [Formula: see text]-[Formula: see text] 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 [Formula: see text], and give a [Formula: see text]-approximate algorithm for the same. We also analyze the version of tracking [Formula: see text]-[Formula: see text] 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 [Formula: see text], and a sequence of trackers [Formula: see text], returns the unique [Formula: see text]-[Formula: see text] path in G that corresponds to [Formula: see text], if one exists.