A Randomized Polynomial Kernelization for Vertex Cover with a Smaller Parameter

DOI10.4230/LIPICS.ESA.2016.59zbMATH Open1397.68103arXiv1611.06795OpenAlexW2948443822MaRDI QIDQ4606331FDOQ4606331

Stefan Kratsch

Publication date: 2 March 2018

Abstract: 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 $XsubseteqV$ 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 $pleqk$ 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 $ell=k-(2LP(G)-MM(G))$. They give an algorithm of running time $O^{*}(3^{e}ll)$, proving that Vertex Cover is FPT in $ell$. It can be easily observed that $ellleqp$ whereas $p$ cannot be bounded in terms of $ell$ alone. We complement the work of Garg and Philip by proving that Vertex Cover admits a randomized polynomial kernelization in terms of $ell$, i.e., an efficient preprocessing to size polynomial in $ell$. This improves over parameter $p=k-LP(G)$ for which this was previously known (Kratsch and Wahlstr"om FOCS 2012).

Full work available at URL: https://arxiv.org/abs/1611.06795

zbMATH Keywords

parameterized complexityvertex coverkernelization

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Randomized algorithms (68W20) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70)

Cited In (9)

• Rank Vertex Cover as a Natural Problem for Algebraic Compression
• Polynomial kernels for vertex cover parameterized by small degree modulators
• Polynomial Kernels for Hitting Forbidden Minors under Structural Parameterizations.
• New Algorithms for Edge Induced König-Egerváry Subgraph Based on Gallai-Edmonds Decomposition
• Partially Polynomial Kernels for Set Cover and Test Cover
• Smaller Parameters for Vertex Cover Kernelization
• Vertex cover kernelization revisited. Upper and lower bounds for a refined parameter
• A randomized polynomial kernel for subset feedback vertex set
• Title not available (Why is that?)

Recommendations

• Title not available (Why is that?) 👍 👎
• Title not available (Why is that?) 👍 👎
• A Randomized Polynomial Kernelization for Vertex Cover with a Smaller Parameter 👍 👎
• Vertex cover kernelization revisited. Upper and lower bounds for a refined parameter 👍 👎
• Smaller Parameters for Vertex Cover Kernelization 👍 👎
• A randomized polynomial kernel for subset feedback vertex set 👍 👎
• A Randomized Polynomial Kernel for Subset Feedback Vertex Set 👍 👎
• Polynomial kernels for vertex cover parameterized by small degree modulators 👍 👎
• Solving vertex cover in polynomial time on hyperbolic random graphs 👍 👎
• A Randomised Approximation Algorithm for the Partial Vertex Cover Problem in Hypergraphs 👍 👎

This page was built for publication: A Randomized Polynomial Kernelization for Vertex Cover with a Smaller Parameter

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4606331)