We look forward to seeing you in person in 3401 Siebel Center.
Abstract: A feedback vertex set is a subset of vertices whose deletion makes the graph acyclic. FVS asks for a minimum-cost feedback vertex set. A pseudoforest deletion set is a subset of vertices whose deletion ensures that each connected component contains at most one cycle. PFD asks for a minimum-cost pseudoforest deletion set. Both these problems are NP-hard. Approximation algorithms for these problems have relied on the local ratio technique which have subsequently led to primal-dual algorithms via LPs, but these LPs were not known to be solvable efficiently. In this talk, I will discuss polynomial time solvable LPs that achieve the best possible approximation factor for both FVS and PFDS. I will also discuss a connection to the densest subgraph problem which inspired the our formulations.
Based on joint work with Karthekeyan Chandrasekaran (UIUC), Chandra Chekuri (UIUC), Samuel Fiorini (Université libre de Bruxelles) and Stefan Weltge (Technische Universität München). https://arxiv.org/abs/2303.12850.
