PACE 2019 (Track Vertex Cover Exact)

Vertex Cover

Given: A graph.

Task: Output a vertex cover of smallest size.

What is a vertex cover?

An undirected graph or simply a graph is a pair $G=(V,E)$ where $V\neq \emptyset$ is a set of vertices and $E \subseteq \{ \{u, v\} \subseteq V : u \neq v \}$ is a set of edges.

A vertex cover of a graph $G=(V,E)$ is a set $S\subseteq V$ such that for every edge $\{u,v\} \in E$ we have $\{u,v\} \cap S \neq \emptyset$.

Input format

See Details


1a. Exact Track


[ChenKanjXia06]: Chen J., Kanj I.A., Xia G. Improved Parameterized Upper Bounds for Vertex Cover. In: Královič R., Urzyczyn P. (eds) Mathematical Foundations of Computer Science (MFCS’06). Lecture Notes in Computer Science, vol 4162. Springer. 2006.

[CyganEtAl15]: Marek Cygan, Fedor V. Fomin, Łukasz Kowalik, Daniel Lokshtanov, Daniel Marx, Marcin Pilipczuk, Michał Pilipczuk, Saket Saurabh: Parameterized Algorithms. ISBN 978-3-319-35702-7. Theoretical Computer Science. Springer. 2015.

[DonweyFellows13]: Rod Downey, Michael R. Fellows. Fundamentals of Parameterized Complexity. Texts in Computer Science. Springer. 2013.

[Niedermeier06]: Rolf Niedermeier.
Invitation to Fixed Parameter Algorithms. Oxford Lecture Series in Mathematics And Its Applications. Oxford University Press. 2006.

[Wikipedia]: Wikipedia contributors, “Vertex cover,” Wikipedia, The Free Encyclopedia. (accessed November 28, 2018).