Fast algorithm for planar-F-deletion via protrusion decompostion

Eun Jung Kim (CNRS Paris)

When: May 13, 2pm

Where: room G2.91b/G215

Abstract

We present a linear-time algorithm to compute a decomposition scheme for graphs G that have a set X of V (G), called a treewidth modulator, such that the treewidth of G − X is bounded by a constant. Our decomposition, called a protrusion decomposition, is the cornerstone in obtaining the following two main results: one is a linear kernel for a range of problems on the class of H-topological-minor-free graphs, for any fixed graph H, and the other is a single-exponential algorithms for a range of graph modification problems. The techniques and applications are discussed with possible direction for further study.