TY - GEN

T1 - Bridge-depth characterizes which structural parameterizations of vertex cover admit a polynomial kernel

AU - Bougeret, Marin

AU - Jansen, Bart M.P.

AU - Sau, Ignasi

PY - 2020/6/1

Y1 - 2020/6/1

N2 - 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 F, such as forests, graphs of bounded tree-depth, and graphs of maximum degree two. We set out to find the most general graph classes F for which Vertex Cover parameterized by the vertex-deletion distance of the input graph to F, admits a polynomial kernelization. We give a complete characterization of the minor-closed graph families F 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 F 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.

AB - 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 F, such as forests, graphs of bounded tree-depth, and graphs of maximum degree two. We set out to find the most general graph classes F for which Vertex Cover parameterized by the vertex-deletion distance of the input graph to F, admits a polynomial kernelization. We give a complete characterization of the minor-closed graph families F 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 F 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.

KW - Bridge-depth

KW - Parameterized complexity

KW - Polynomial kernel

KW - Structural parameterization

KW - Vertex cover

UR - http://www.scopus.com/inward/record.url?scp=85089354899&partnerID=8YFLogxK

U2 - 10.4230/LIPIcs.ICALP.2020.16

DO - 10.4230/LIPIcs.ICALP.2020.16

M3 - Conference contribution

AN - SCOPUS:85089354899

T3 - Leibniz International Proceedings in Informatics, LIPIcs

BT - 47th International Colloquium on Automata, Languages, and Programming, ICALP 2020

A2 - Czumaj, Artur

A2 - Dawar, Anuj

A2 - Merelli, Emanuela

PB - Schloss Dagstuhl - Leibniz-Zentrum für Informatik

T2 - 47th International Colloquium on Automata, Languages, and Programming, ICALP 2020

Y2 - 8 July 2020 through 11 July 2020

ER -