Vertex deletion into bipartite permutation graphs

A permutation graph can be defined as an intersection graph of segments whose endpoints lie on two parallel lines, one on each. A bipartite permutation graph is a permutation graph which is bipartite. 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 NP-complete by the classical result of Lewis and Yannakakis (JCSS ’80).

 

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 and exploit the structural properties of the shortest hole in such graphs. We use it to obtain an algorithm for the bipartite permutation vertex deletion problem with running time O(9^k \cdot n^9), and also give a polynomial-time 9-approximation algorithm.