Deutsch
 
Benutzerhandbuch Datenschutzhinweis Impressum Kontakt
  DetailsucheBrowse

Datensatz

DATENSATZ AKTIONENEXPORT

Freigegeben

Forschungspapier

Raising The Bar For Vertex Cover: Fixed-parameter Tractability Above A Higher Guarantee

MPG-Autoren
/persons/resource/persons71823

Philip,  Geevarghese
Algorithms and Complexity, MPI for Informatics, Max Planck Society;

Externe Ressourcen
Es sind keine Externen Ressourcen verfügbar
Volltexte (frei zugänglich)

arXiv:1509.03990.pdf
(Preprint), 230KB

Ergänzendes Material (frei zugänglich)
Es sind keine frei zugänglichen Ergänzenden Materialien verfügbar
Zitation

Garg, S., & Philip, G. (2015). Raising The Bar For Vertex Cover: Fixed-parameter Tractability Above A Higher Guarantee. Retrieved from http://arxiv.org/abs/1509.03990.


Zitierlink: http://hdl.handle.net/11858/00-001M-0000-0028-8200-9
Zusammenfassung
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.