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
Tracks
1a. Exact Track
Literature
[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).