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.)