2026-07-22T16:56:50Z https://drops.dagstuhl.de/oai

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

Lossy Kernels for Hitting Subgraphs Eiben, Eduard Hermelin, Danny Ramanujan, M. S. parameterized algorithms lossy kernelization graph theory In this paper, we study the Connected H-hitting Set and Dominating Set problems from the perspective of approximate kernelization, a framework recently introduced by Lokshtanov et al. [STOC 2017]. For the Connected H-hitting set problem, we obtain an \alpha-approximate kernel for every \alpha>1 and complement it with a lower bound for the natural weighted version. We then perform a refined analysis of the tradeoff between the approximation factor and kernel size for the Dominating Set problem on d-degenerate graphs and provide an interpolation of approximate kernels between the known d^2-approximate kernel of constant size and 1-approximate kernel of size k^{O(d^2)}. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Eduard Eiben and Danny Hermelin and M. S. Ramanujan 2017 Is Part Of LIPIcs, Volume 83, 42nd International Symposium on Mathematical Foundations of Computer Science (MFCS 2017) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.MFCS.2017.67 urn:nbn:de:0030-drops-80955 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.MFCS.2017.67 eng https://creativecommons.org/licenses/by/3.0/legalcode