2026-08-10T16:18:04Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:6406 2024-03-06T10:38:10Z ddc:004 open_access

A Randomized Polynomial Kernelization for Vertex Cover with a Smaller Parameter Kratsch, Stefan Vertex cover parameterized complexity kernelization In the Vertex Cover problem we are given a graph G=(V,E) and an integer k and have to determine whether there is a set X subseteq V of size at most k such that each edge in E has at least one endpoint in X. The problem can be easily solved in time O^*(2^k), making it fixed-parameter tractable (FPT) with respect to k. While the fastest known algorithm takes only time O^*(1.2738^k), much stronger improvements have been obtained by studying parameters that are smaller than k. Apart from treewidth-related results, the arguably best algorithm for Vertex Cover runs in time O^*(2.3146^p), where p = k - LP(G) is only the excess of the solution size k over the best fractional vertex cover [Lokshtanov et al., TALG 2014]. Since p <= k but k cannot be bounded in terms of p alone, this strictly increases the range of tractable instances. Recently, Garg and Philip (SODA 2016) greatly contributed to understanding the parameterized complexity of the Vertex Cover problem. They prove that 2LP(G) - MM(G) is a lower bound for the vertex cover size of G, where MM(G) is the size of a largest matching of G, and proceed to study parameter l = k - (2LP(G)-MM(G)). They give an algorithm of running time O^*(3^l), proving that Vertex Cover is FPT in l. It can be easily observed that l <= p whereas p cannot be bounded in terms of l alone. We complement the work of Garg and Philip by proving that Vertex Cover admits a randomized polynomial kernelization in terms of l, i.e., an efficient preprocessing to size polynomial in l. This improves over parameter p = k - LP(G) for which this was previously known [Kratsch and Wahlström, FOCS 2012]. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Stefan Kratsch 2016 Is Part Of LIPIcs, Volume 57, 24th Annual European Symposium on Algorithms (ESA 2016) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.ESA.2016.59 urn:nbn:de:0030-drops-64066 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ESA.2016.59 eng https://creativecommons.org/licenses/by/3.0/legalcode