Constant Factor Approximation for Tracking Paths and Fault Tolerant Feedback Vertex Set

Consider a vertex-weighted graph \(G\) with a source \(s\) and a target \(t\). Tracking Paths requires finding a minimum weight set of vertices (called trackers) such that the sequence of trackers in each path from \(s\) to \(t\) is unique. In this work, we derive a factor \(6\)-approximation algorithm for Tracking Paths in 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 related \(r\)-Fault Tolerant Feedback Vertex Set problem. There, for a fixed integer \(r\) and a given vertex-weighted graph \(G\), the task is to find a minimum weight set of vertices intersecting every cycle of \(G\) in at least \(r+1\) vertices. We give a factor \(\mathcal{O}(r)\) approximation algorithm for \(r\)-Fault Tolerant Feedback Vertex Set if \(r\) is a constant.

This is joint work with Václav Blažej, Pratibha Choudhary, Dušan Knop, Ondřej Suchý, and Tomáš Valla.

Recording