Parameterized complexity of Distance-Hereditary Vertex Deletion

A graph is distance-hereditary if for any pair of vertices, their distance in every connected induced subgraph containing both vertices is the same as their distance in the original graph. Distance-hereditary graphs are exactly the graphs with rank-width at most 1. The Distance-Hereditary Vertex Deletion problem asks, given a graph G on n vertices and an integer k, whether there is a set S of at most k vertices in G such that G−S is distance-hereditary. We prove that it can be solved in time 2^{O(k)}poly(n). In this talk, we sketch the proof, and see its applications. This is joint work with Eduard Eiben and Robert Ganian.