• Media type: Text; Electronic Conference Proceeding; E-Article
  • Title: Polynomial Kernel for Immersion Hitting in Tournaments
  • Contributor: Bożyk, Łukasz [Author]; Pilipczuk, Michał [Author]
  • imprint: Schloss Dagstuhl – Leibniz-Zentrum für Informatik, 2022
  • Language: English
  • DOI: https://doi.org/10.4230/LIPIcs.ESA.2022.26
  • Keywords: protrusion ; graph immersion ; kernelization ; tournament
  • Origination:
  • Footnote: Diese Datenquelle enthält auch Bestandsnachweise, die nicht zu einem Volltext führen.
  • Description: 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.
  • Access State: Open Access