Nie jesteś zalogowany | zaloguj się

Wydział Matematyki, Informatyki i Mechaniki Uniwersytetu Warszawskiego

  • Skala szarości
  • Wysoki kontrast
  • Negatyw
  • Podkreślenie linków
  • Reset

Aktualności — Wydarzenia

Sem. Algorytmika


Vertex deletion into bipartite permutation graphs

Prelegent: Łukasz Bożyk

2021-03-04 12:15

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.