A New Framework for Kernelization Lower Bounds: The Case of Maximum Minimal Vertex Cover - LIRMM - Laboratoire d’Informatique, de Robotique et de Microélectronique de Montpellier Access content directly
Conference Papers Year : 2021

A New Framework for Kernelization Lower Bounds: The Case of Maximum Minimal Vertex Cover

Abstract

In the Maximum Minimal Vertex Cover (MMVC) problem, we are given a graph G and a positive integer k, and the objective is to decide whether G contains a minimal vertex cover of size at least k. Motivated by the kernelization of MMVC with parameter k, our main contribution is to introduce a simple general framework to obtain lower bounds on the degrees of a certain type of polynomial kernels for vertex-optimization problems, which we call lop-kernels. Informally, this type of kernels is required to preserve large optimal solutions in the reduced instance, and captures the vast majority of existing kernels in the literature. As a consequence of this framework, we show that the trivial quadratic kernel for MMVC is essentially optimal, answering a question of Boria et al. [Discret. Appl. Math. 2015], and that the known cubic kernel for Maximum Minimal Feedback Vertex Set is also essentially optimal. On the positive side, given the (plausible) non-existence of subquadratic kernels for MMVC on general graphs, we provide subquadratic kernels on H-free graphs for several graphs H, such as the bull, the paw, or the complete graphs, by making use of the Erdős-Hajnal property in order to find an appropriate decomposition. Finally, we prove that MMVC does not admit polynomial kernels parameterized by the size of a minimum vertex cover of the input graph, even on bipartite graphs, unless NP ⊆ coNP/poly. This indicates that parameters smaller than the solution size are unlike to yield polynomial kernels for MMVC.
Fichier principal
Vignette du fichier
LIPIcs-IPEC-2021-4.pdf (1003.26 Ko) Télécharger le fichier
Origin Files produced by the author(s)

Dates and versions

lirmm-03526704 , version 1 (14-01-2022)

Licence

Identifiers

Cite

Júlio Araújo, Marin Bougeret, Victor Campos, Ignasi Sau. A New Framework for Kernelization Lower Bounds: The Case of Maximum Minimal Vertex Cover. IPEC 2021 - 16th International Symposium on Parameterized and Exact Computation, Sep 2021, Virtual, Portugal. pp.4:1-4:19, ⟨10.4230/LIPIcs.IPEC.2021.4⟩. ⟨lirmm-03526704⟩
60 View
700 Download

Altmetric

Share

Gmail Mastodon Facebook X LinkedIn More