Polynomial Time Algorithms for Tracking Path Problems
Pratibha Choudhary · Lecture notes in computer science · 2020
Abstract Given a graphG, and terminal verticessandt, theTracking Pathsproblem asks to compute a set of minimum number of vertices to be marked as trackers, such that the sequence of trackers encountered in each $$s$$ s - $$t$$ t path is unique.Tracking PathsisNP-hard in both directed and undirected graphs in general. In this paper we give a collection of polynomial time algorithms for some restricted versions ofTracking Paths. We prove thatTracking Pathsis polynomial time solvable for undirected chordal graphs and tournament graphs. We also show thatTracking PathsisNP-hard in graphs with bounded maximum degree $$\Delta \ge 6$$ Δ≥6 , and give a $$2(\Delta +1)$$ 2(Δ+1) -approximate algorithm for this case. Further, we give a polynomial time algorithm which, given an undirected graphG, a tracking set $$T\subseteq V(G)$$ T⊆V(G) , and a sequence of trackers $$\pi $$ π , returns the unique $$s$$ s - $$t$$ t path inGthat corresponds to $$\pi $$ π , if one exists. Finally we analyze the version of tracking $$s$$ s - $$t$$ t paths where paths are tracked using edges instead of vertices, and we give a polynomial time algorithm for the same.