Description
EGERVÁRY SZEMINÁRIUM
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 nearly the best possible
approximation factor for both FVS and PFDS.
Based on joint work with Karthik Chandrasekaran and Chandra Chekuri.