For a finite <undirected graph> $G=(V,E)$, a <vertex cover> is a <subset> $C\subseteq V$ meeting every <edge>: for every $\{u,v\}\in E$, at least one of $u,v$ belongs to $C$. \b[The optimization problem asks for a <vertex cover> of minimum <cardinality>.] Its usual decision version also supplies an <integer> $k$ and asks whether one exists with $|C|\leq k$.

Solution

Past exam of the computer science course of the University of Oxford / 2018 / Algorithms / 2 / a / Solution

 Solution (source code)