hide
Free keywords:
Computer Science, Data Structures and Algorithms, cs.DS
Abstract:
We investigate the following above-guarantee parameterization of the
classical Vertex Cover problem: Given a graph $G$ and $k\in\mathbb{N}$ 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)\geq{LP}\geq{MM}$, 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.
