Constant factor approximation for tracking paths and fault tolerant feedback vertex set

• Published in: Discrete optimization 2023-02, Vol.47, p.100756, Article 100756
• Main Authors: Blažej, Václav, Choudhary, Pratibha, Knop, Dušan, Křišťan, Jan Matyáš, Suchý, Ondřej, Valla, Tomáš
• Format: Article
• Language: English
• Subjects: Approximate algorithms; Feedback vertex set; Tracking paths
• ISSN: 1572-5286; 1873-636X
• DOI: 10.1016/j.disopt.2022.100756

Consider 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 O(r) approximation algorithm for r-Fault Tolerant Feedback Vertex Set if r is a constant. •We derive the first constant factor approximation algorithm for the Tracking Paths problem.•We give a factor O(r) approximation algorithm for the related r-Fault Tolerant Feedback Vertex Set.•We also show that Weighted Vertex Multicut in Forests has a 2-approximation.