arXiv WAOA 2021 DO 📺 WAOA 2021 | tags:[ approximation graph theory ]

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

with Pratibha Choudhary, Dušan Knop, Jan Matyáš Křišťan, Ondřej Suchý, and Tomáš VallaConsider a vertex-weighted graph $G$ with a source $s$ and a target $t$.
*Tracking Paths* requires finding a minimum weight set of vertices (*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.