DROPS

Document

DOI: 10.4230/LIPIcs.ESA.2022.26

Polynomial Kernel for Immersion Hitting in Tournaments

Authors: Łukasz Bożyk and Michał Pilipczuk

Published in: LIPIcs, Volume 244, 30th Annual European Symposium on Algorithms (ESA 2022)

Abstract

For a fixed simple digraph H without isolated vertices, we consider the problem of deleting arcs from a given tournament to get a digraph which does not contain H as an immersion. We prove that for every H, this problem admits a polynomial kernel when parameterized by the number of deleted arcs. The degree of the bound on the kernel size depends on H.

Cite as

Łukasz Bożyk and Michał Pilipczuk. Polynomial Kernel for Immersion Hitting in Tournaments. In 30th Annual European Symposium on Algorithms (ESA 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 244, pp. 26:1-26:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)

Copy BibTex To Clipboard

@InProceedings{bozyk_et_al:LIPIcs.ESA.2022.26,
  author =	{Bo\.{z}yk, {\L}ukasz and Pilipczuk, Micha{\l}},
  title =	{{Polynomial Kernel for Immersion Hitting in Tournaments}},
  booktitle =	{30th Annual European Symposium on Algorithms (ESA 2022)},
  pages =	{26:1--26:17},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-247-1},
  ISSN =	{1868-8969},
  year =	{2022},
  volume =	{244},
  editor =	{Chechik, Shiri and Navarro, Gonzalo and Rotenberg, Eva and Herman, Grzegorz},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ESA.2022.26},
  URN =		{urn:nbn:de:0030-drops-169642},
  doi =		{10.4230/LIPIcs.ESA.2022.26},
  annote =	{Keywords: kernelization, graph immersion, tournament, protrusion}
}

Document

DOI: 10.4230/LIPIcs.IPEC.2020.5

Vertex Deletion into Bipartite Permutation Graphs

Authors: Łukasz Bożyk, Jan Derbisz, Tomasz Krawczyk, Jana Novotná, and Karolina Okrasa

Published in: LIPIcs, Volume 180, 15th International Symposium on Parameterized and Exact Computation (IPEC 2020)

Abstract

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.

Cite as

Łukasz Bożyk, Jan Derbisz, Tomasz Krawczyk, Jana Novotná, and Karolina Okrasa. Vertex Deletion into Bipartite Permutation Graphs. In 15th International Symposium on Parameterized and Exact Computation (IPEC 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 180, pp. 5:1-5:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)

Copy BibTex To Clipboard

@InProceedings{bozyk_et_al:LIPIcs.IPEC.2020.5,
  author =	{Bo\.{z}yk, {\L}ukasz and Derbisz, Jan and Krawczyk, Tomasz and Novotn\'{a}, Jana and Okrasa, Karolina},
  title =	{{Vertex Deletion into Bipartite Permutation Graphs}},
  booktitle =	{15th International Symposium on Parameterized and Exact Computation (IPEC 2020)},
  pages =	{5:1--5:16},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-172-6},
  ISSN =	{1868-8969},
  year =	{2020},
  volume =	{180},
  editor =	{Cao, Yixin and Pilipczuk, Marcin},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.IPEC.2020.5},
  URN =		{urn:nbn:de:0030-drops-133087},
  doi =		{10.4230/LIPIcs.IPEC.2020.5},
  annote =	{Keywords: permutation graphs, comparability graphs, partially ordered set, graph modification problems}
}

Search Results

Documents authored by Bożyk, Łukasz

Polynomial Kernel for Immersion Hitting in Tournaments

Abstract

Cite as

Vertex Deletion into Bipartite Permutation Graphs

Abstract

Cite as

Thanks for your feedback!

Could not send message