Bożyk, Łukasz
[Author];
Derbisz, Jan
[Author];
Krawczyk, Tomasz
[Author];
Novotná, Jana
[Author];
Okrasa, Karolina
[Author]
;
Łukasz Bożyk and Jan Derbisz and Tomasz Krawczyk and Jana Novotná and Karolina Okrasa
[Contributor]
Footnote:
Diese Datenquelle enthält auch Bestandsnachweise, die nicht zu einem Volltext führen.
Description:
A permutation graph can be defined as an intersection graph of segments whose endpoints lie on two parallel lines 𝓁₁ and 𝓁₂, 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 NP-complete by the classical result of Lewis and Yannakakis [John M. Lewis and Mihalis Yannakakis, 1980]. 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 a such 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.