Module covering 

Set cover, weighted set cover, vertex cover, and hitting set algorithms.

• Greedy log-approximation for (weighted) set cover
• 2-approximation vertex cover via maximal matching
• König’s theorem exact minimum vertex cover for bipartite graphs
• Greedy hitting set

Functions

greedy_set_cover

Greedy set cover (unweighted): at each step, pick the set that covers the most uncovered elements of universe.

hitting_set

Greedy hitting set: find a small set H ⊆ {0..universe-1} such that every input set contains at least one element of H.

min_vertex_cover_bip

Exact minimum vertex cover for a bipartite graph via König’s theorem.

vertex_cover_2approx

2-approximation vertex cover via maximal matching.

weighted_set_cover

Greedy weighted set cover: at each step, pick the set with the lowest cost per newly-covered element.

Type Aliases

CoveringResult

Result type for covering operations.