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 |
ABSTRACT
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.
