CS 269S, Spring 2021: Theory Seminar

June 4, 2021, 1:00 – 1:50:

Vertex Deletion into Bipartite Permutation Graphs

Haleh Havvaei

A permutation graph can be defined as an intersection graph of segments whose endpoints lie on two parallel lines ${\ell }_1$ and ${\ell }_2$, one on each. A bipartite permutation graph is a permutation graph which is bipartite. In this paper we study the parameterized complexity of the bipartite permutation vertex deletion problem, which asks, for a given $n$-vertex graph, whether we can remove at most $k$ vertices to obtain a bipartite permutation graph. This problem is $\mathsf{NP}$-complete by the classical result of Lewis and Yannakakis. We analyze the structure of the so-called almost bipartite permutation graphs which may contain holes (large induced cycles) in contrast to bipartite permutation graphs. We exploit the structural properties of the shortest hole in such a graph. We use it to obtain an algorithm for the bipartite permutation vertex deletion problem with running time $f(k)n^{O(1)}$, and also give a polynomial-time $9$-approximation algorithm.

(Based on an IPEC 2020 paper by Łukasz Bożyk, Jan Derbisz, Tomasz Krawczyk, Jana Novotná and Karolina Okrasa.)