Module edge_cover 

Edge cover algorithms (ALGO-MA-002).

An edge cover is a set of edges such that every vertex in the graph is incident to at least one edge in the set. An edge cover exists if and only if the graph has no isolated vertices.

We compute a minimum edge cover via a greedy maximal matching followed by covering unmatched vertices with any incident edge. For graphs without isolated vertices, the result size equals n - |matching|, which is optimal by König’s theorem.

Functions

is_edge_cover

Check whether a set of edge IDs forms a valid edge cover.

minimum_edge_cover

Compute a minimum edge cover.