Raising The Bar For V<scp>ertex</scp> C<scp>over</scp>: Fixed-parameter Tractability Above A Higher Guarantee

DOI10.1137/1.9781611974331.CH80zbMATH Open1398.68234arXiv1509.03990OpenAlexW2952307946MaRDI QIDQ4575661

Author name not available (Why is that?)

Publication date: 16 July 2018

Published in: (Search for Journal in Brave)

Abstract: We investigate the following above-guarantee parameterization of the classical Vertex Cover problem: Given a graph $G$ and $kinmathbbN$ as input, does $G$ have a vertex cover of size at most $(2LP-MM)+k$? Here $MM$ is the size of a maximum matching of $G$, $LP$ is the value of an optimum solution to the relaxed (standard) LP for Vertex Cover on $G$, and $k$ is the parameter. Since $(2LP-MM)geqLPgeqMM$, this is a stricter parameterization than those---namely, above-$MM$, and above-$LP$---which have been studied so far. We prove that Vertex Cover is fixed-parameter tractable for this stricter parameter $k$: We derive an algorithm which solves Vertex Cover in time $O^{*}(3^k)$, pushing the envelope further on the parameterized tractability of Vertex Cover.

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

Mathematics Subject Classification ID

No records found.

This page was built for publication: Raising The Bar For V<scp>ertex</scp> C<scp>over</scp>: Fixed-parameter Tractability Above A Higher Guarantee

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