2026-07-23T22:06:52Z https://drops.dagstuhl.de/oai

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

Bridge-Depth Characterizes Which Structural Parameterizations of Vertex Cover Admit a Polynomial Kernel Bougeret, Marin Jansen, Bart M. P. Sau, Ignasi vertex cover parameterized complexity polynomial kernel structural parameterization bridge-depth We study the kernelization complexity of structural parameterizations of the Vertex Cover problem. Here, the goal is to find a polynomial-time preprocessing algorithm that can reduce any instance (G,k) of the Vertex Cover problem to an equivalent one, whose size is polynomial in the size of a pre-determined complexity parameter of G. A long line of previous research deals with parameterizations based on the number of vertex deletions needed to reduce G to a member of a simple graph class ℱ, such as forests, graphs of bounded tree-depth, and graphs of maximum degree two. We set out to find the most general graph classes ℱ for which Vertex Cover parameterized by the vertex-deletion distance of the input graph to ℱ, admits a polynomial kernelization. We give a complete characterization of the minor-closed graph families ℱ for which such a kernelization exists. We introduce a new graph parameter called bridge-depth, and prove that a polynomial kernelization exists if and only if ℱ has bounded bridge-depth. The proof is based on an interesting connection between bridge-depth and the size of minimal blocking sets in graphs, which are vertex sets whose removal decreases the independence number. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Marin Bougeret and Bart M. P. Jansen and Ignasi Sau 2020 Is Part Of LIPIcs, Volume 168, 47th International Colloquium on Automata, Languages, and Programming (ICALP 2020) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.ICALP.2020.16 urn:nbn:de:0030-drops-124238 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2020.16 eng https://creativecommons.org/licenses/by/3.0/legalcode