Constant Factor Approximation for Tracking Paths and Fault Tolerant Feedback Vertex Set
Václav Blažej, Pratibha Choudhary, Dušan Knop, Jan Matyáš Křišťan, Ondřej Suchý, Tomáš Valla · Lecture notes in computer science · 2021
Abstract Consider a vertex-weighted graphGwith a sourcesand a targett.Tracking Pathsrequires finding a minimum weight set of vertices (trackers) such that the sequence of trackers in each path fromstotis unique. In this work, we derive a factor 66-approximation algorithm forTracking Pathsin weighted graphs and a factor 4-approximation algorithm if the input is unweighted. This is the first constant factor approximation for this problem. While doing so, we also study approximation of the closely relatedr-Fault Tolerant Feedback Vertex Setproblem. There, for a fixed integer rand a given vertex-weighted graphG, the task is to find a minimum weight set of vertices intersecting every cycle of Gin at least $$r+1$$ r+1 vertices. We give a factor $$\mathcal {O}(r^2)$$ O(r2) approximation algorithm forr-Fault Tolerant Feedback Vertex Setifris a constant.