2026-07-24T05:17:05Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:15387 2024-03-06T10:55:37Z ddc:004 open_access

A New Framework for Kernelization Lower Bounds: The Case of Maximum Minimal Vertex Cover Araújo, Júlio Bougeret, Marin Campos, Victor Sau, Ignasi Maximum minimal vertex cover parameterized complexity polynomial kernel kernelization lower bound Erdős-Hajnal property induced subgraphs 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. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Júlio Araújo and Marin Bougeret and Victor Campos and Ignasi Sau 2021 Is Part Of LIPIcs, Volume 214, 16th International Symposium on Parameterized and Exact Computation (IPEC 2021) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.IPEC.2021.4 urn:nbn:de:0030-drops-153879 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.IPEC.2021.4 eng https://creativecommons.org/licenses/by/4.0/legalcode