Neeldhara Misra

From FVS to F-deletion: the Story of a Simple Algorithm

The VCLA hosted a talk by Neeldhara Misra on May 21st, 2012 together with the Austrian Agency in International Cooperation and Research (OeAD).

DATE:Monday, May 21, 2012
TIME:16:00 (s.t.)
VENUE:Seminar room Gödel


We describe a randomized constant ratio approximation algorithm for the F-deletion problem, where we are given a family of graphs F and we are looking for the smallest subset of vertices whose deletion removes all minor models of graphs from F. In other words, if G is the input graph and S is a solution, then G-S contains no graph from F as a minor.

We use feedback vertex set as a case in point (where the family F consists of just the triangle) and describe how the ideas can be generalized. We introduce the notion of an alpha-cover, which is a generic property - once a graph admits an alpha-cover, the path to such an approximation algorithm is clear. We will briefly touch on the notion of lossless protrusions and fast protrusion replacement which enable us to prepocess the graph to the point where it admits an alpha-cover.

Comments are closed.