Kernelization Dichotomies for Hitting Subgraphs Under Structural Parameterizations - LIRMM - Laboratoire d’Informatique, de Robotique et de Microélectronique de Montpellier
Communication Dans Un Congrès Année : 2024

Kernelization Dichotomies for Hitting Subgraphs Under Structural Parameterizations

Marin Bougeret
Ignasi Sau

Résumé

For a fixed graph H, the H-Subgraph Hitting problem consists in deleting the minimum number of vertices from an input graph to obtain a graph without any occurrence of H as a subgraph. This problem can be seen as a generalization of Vertex Cover, which corresponds to the case H = K2. We initiate a study of H-Subgraph Hitting from the point of view of characterizing structural parameterizations that allow for polynomial kernels, within the recently active framework of taking as the parameter the number of vertex deletions to obtain a graph in a "simple" class C. Our main contribution is to identify graph parameters that, when H-Subgraph Hitting is parameterized by the vertex-deletion distance to a class C where any of these parameters is bounded, and assuming standard complexity assumptions and that H is biconnected, allow us to prove the following sharp dichotomy: the problem admits a polynomial kernel if and only if H is a clique. These new graph parameters are inspired by the notion of C-elimination distance introduced by Bulian and Dawar [Algorithmica 2016], and generalize it in two directions. Our results also apply to the version of the problem where one wants to hit H as an induced subgraph, and imply in particular, that the problems of hitting minors and hitting (induced) subgraphs have a substantially different behavior with respect to the existence of polynomial kernels under structural parameterizations.
Fichier principal
Vignette du fichier
LIPIcs.ICALP.2024.33.pdf (1.03 Mo) Télécharger le fichier
Origine Fichiers produits par l'(les) auteur(s)
Licence

Dates et versions

lirmm-04700560 , version 1 (17-09-2024)

Licence

Identifiants

Citer

Marin Bougeret, Bart M.P. Jansen, Ignasi Sau. Kernelization Dichotomies for Hitting Subgraphs Under Structural Parameterizations. ICALP 2024 - 51st International Colloquium on Automata, Languages, and Programming, Jul 2024, Tallinn, Estonia. pp.33:1-33:20, ⟨10.4230/LIPIcs.ICALP.2024.33⟩. ⟨lirmm-04700560⟩
11 Consultations
10 Téléchargements

Altmetric

Partager

More