A Randomized Polynomial Kernelization for Vertex Cover with a Smaller Parameter

DOI10.4230/LIPICS.ESA.2016.59MaRDI QIDQ4606331zbMATH OpenOpenAlexFDO

Authors Stefan Kratsch

Publication date 2 March 2018

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)

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^{\ast }(2^k)$, making it fixed-parameter tractable (FPT) with respect to $k$. While the fastest known algorithm takes only time $O^{\ast }(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^{\ast }(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^{\ast }(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).

Recommendations

• A randomized polynomial kernelization for vertex cover with a smaller parameter
• Polynomial kernels for vertex cover parameterized by small degree modulators
• Smaller parameters for vertex cover kernelization
• Vertex cover kernelization revisited: upper and lower bounds for a refined parameter
• Vertex cover kernelization revisited. Upper and lower bounds for a refined parameter
• A randomized polynomial kernel for subset feedback vertex set
• A randomized polynomial kernel for subset feedback vertex set
• Solving vertex cover in polynomial time on hyperbolic random graphs
• Solving vertex cover in polynomial time on hyperbolic random graphs
• A randomised approximation algorithm for the partial vertex cover problem in hypergraphs

Cited in

(14)

• Polynomial Kernels for Hitting Forbidden Minors under Structural Parameterizations.
• Faster parameterized algorithms using linear programming
• New Algorithms for Edge Induced König-Egerváry Subgraph Based on Gallai-Edmonds Decomposition
• Rank vertex cover as a natural problem for algebraic compression
• LP can be a cure for parameterized problems
• Vertex cover kernelization revisited. Upper and lower bounds for a refined parameter
• A randomized polynomial kernelization for vertex cover with a smaller parameter
• Polynomial kernels for vertex cover parameterized by small degree modulators
• On kernelization for edge dominating set under structural parameters
• Partially Polynomial Kernels for Set Cover and Test Cover
• Vertex cover kernelization revisited: upper and lower bounds for a refined parameter
• A randomized polynomial kernel for subset feedback vertex set
• Smaller parameters for vertex cover kernelization
• Raising the bar for \textsc{Vertex Cover}: fixed-parameter tractability above a higher guarantee

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)