Module vertex_cover 

Vertex cover algorithms (ALGO-VC-001).

A vertex cover is a set of vertices such that every edge in the graph is incident to at least one vertex in the set. Finding a minimum vertex cover is NP-hard; we provide a greedy 2-approximation.

The greedy algorithm repeatedly picks an uncovered edge and adds both endpoints to the cover. This guarantees the result is at most twice the size of the optimal cover (König 1931 / Gavril 1974).

Functions

is_vertex_cover

Check whether a set of vertices forms a valid vertex cover.

minimum_vertex_cover

Compute a minimum vertex cover using a greedy 2-approximation.