2026-07-21T14:19:01Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:16964 2024-03-06T10:58:50Z ddc:004 open_access

Polynomial Kernel for Immersion Hitting in Tournaments Bożyk, Łukasz Pilipczuk, Michał kernelization graph immersion tournament protrusion 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. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Łukasz Bożyk and Michał Pilipczuk 2022 Is Part Of LIPIcs, Volume 244, 30th Annual European Symposium on Algorithms (ESA 2022) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.ESA.2022.26 urn:nbn:de:0030-drops-169642 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ESA.2022.26 eng https://creativecommons.org/licenses/by/4.0/legalcode