Polynomial kernel for immersion hitting in tournaments

Autor:	Bożyk, Łukasz, Pilipczuk, Michał
Rok vydání:	2022
Předmět:	Computer Science - Data Structures and Algorithms Computer Science - Discrete Mathematics 05C85 F.2.2 G.2.2
Druh dokumentu:	Working Paper
Popis:	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$. Comment: Full version of a paper accepted to ESA 2022
Databáze:	arXiv
Externí odkaz:	http://arxiv.org/abs/2208.07789 Zobrazit plný text záznamu View this record from Arxiv