Deletion problems regarding graphs of bounded rank-width

VCLA will host a talk by O-Joung Kwon on Monday, March 14, 2016.

ABSTRACT

Recently, many researchers have focused on vertex- and edge-deletion problems where the target graph classes are classes with bounded tree-width. Examples of such problems include Vertex Cover, Feedback Vertex Set and Tree-width-w Vertex Deletion. This research direction has led to many interesting results; for instance, for any fixed w, Tree-width-w Vertex Deletion can be solved in single-exponential FPT time parameterized by the solution size. We are interested in generalizing these results to classes of graphs of bounded rank-width (equivalently, clique-width). In this talk, we summarize our results on two special problems, called Block Graph Vertex Deletion and Linear rank-width-1 Vertex Deletion, which can be regarded as starting points for work in this direction. We first show that these problems can be solved in FPT time parameterized by the solution size using a general logical framework, and later observe some ideas for solving these simpler problems even without using this logical framework. At the end, we will also discuss the possibilities of generalizing these results to other problems. This is joint work with Mamadou Kante, Eun Jung Kim, and Christophe Paul.