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 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 -vertex graph, whether we can remove at most
vertices to obtain a bipartite permutation graph. This problem is
-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 , and also give a polynomial-time
-approximation algorithm.
(Based on an
IPEC 2020 paper by Åukasz Bożyk, Jan Derbisz,
Tomasz Krawczyk, Jana Novotná and Karolina Okrasa.)