Minimum Vertex Cover

Given a simple undirected graph $G=(V,E)$ , a vertex cover is a set $C\subseteq V$ such that every edge has at least one endpoint in $C$ :

\forall\{u,v\}\in E,\qquad u\in C \;\text{or}\; v\in C.

The optimization problem asks for a vertex cover of minimum size. Throughout this project, Minimum Vertex Cover is abbreviated MVC and uses the problem identifier minimum_vertex_cover (short command-line alias mvc).

Before implementing your algorithms, review the project-wide Program Interface and Input Files pages.

Graph assumptions

MVC instances use the shared course Graph representation.

Vertices are numbered $0,1,\ldots,n-1$ .
Graphs are simple and undirected.
Graphs need not be connected.
Isolated vertices may appear.

MVC solution format

A solver returns one vertex cover:

{
  "size": 3,
  "vertices": [0, 2, 3]
}

vertices represents a set, so its order is not significant and duplicates are not permitted. size must equal len(vertices). If several minimum covers exist, any one of them is acceptable.

For example:

python src/solve.py example-01.txt \
    --problem mvc \
    --algorithm exhaustive

runs the MVC exhaustive solver through the common course driver.

Solution verifier

Your Checkpoint 2 implementation must provide:

from course.common.graph import Graph


def is_vertex_cover(graph: Graph, vertices: list[int], k: int) -> bool:
    ...

in:

src/student/problems/minimum_vertex_cover/verifier.py

This is the verifier for the decision version of MVC. It returns True exactly when all of the following hold:

vertices contains only valid graph vertices and contains no duplicates;
every edge has at least one endpoint in vertices; and
the certificate contains at most k vertices.

The verifier checks the supplied certificate and threshold. It does not determine whether the cover is minimum and must not call a solving algorithm. Gradescope may import and test the verifier independently of src/solve.py.

A direct implementation can convert the list to a set once and then scan all edges, giving polynomial running time.

Checkpoint 2 exhaustive baseline

Checkpoint 2 uses the project-wide complete-candidate enumeration model. For MVC:

try candidate sizes $k=0,1,2,\ldots$ from small to large;
for each $k$ , enumerate every vertex subset of size $k$ ; and
test each completed subset with is_vertex_cover().

Once the first valid cover is found, it is optimal because every smaller candidate size has already been exhausted.

The Checkpoint 2 baseline should not reject partial subsets, branch on uncovered edges, prune, memoize, use dynamic programming, or use branch-and-bound. Those techniques belong to the improved exact algorithm.

The exhaustive solver must also record:

statistics["candidates"]

Increment this counter exactly once for each complete vertex subset that is actually tested as a candidate cover. Partial states and loop iterations that do not produce a tested complete subset are not candidates.

Checkpoint 3 improved exact search

MVC has a useful structural observation. If an edge $\{u,v\}$ is currently uncovered, every vertex cover must contain at least one of its endpoints. Therefore an exact search may branch into two subproblems:

include u
or
include v

and continue on the remaining uncovered edges. This can avoid enormous portions of the complete-subset search performed by the Checkpoint 2 baseline.

Additional exact improvements may include better edge/vertex selection, reduction rules, an incumbent solution, lower-bound pruning, memoization, or other justified techniques. These are examples rather than a mandated implementation. Your solver must remain exact and you must explain why any pruned work cannot contain a better solution.

Checkpoint 3 lower bound

MVC is a minimization problem, so the required polynomial-time bound is a lower bound:

from course.common.graph import Graph


def lower_bound(graph: Graph) -> int:
    ...

in:

src/student/problems/minimum_vertex_cover/bound.py

If the optimum is $OPT$ , the returned value must always satisfy

\texttt{lower\_bound}(G) \le OPT(G).

One natural source of a lower bound is a maximal matching. The edges of a matching share no endpoints, and covering each matched edge requires selecting at least one distinct endpoint. Therefore the size of any matching is a valid lower bound on the minimum vertex-cover size. A greedily constructed maximal matching is polynomial-time and is sufficient as one possible design.

You are not required to use that particular bound. The returned value must be valid for every legal instance, polynomial-time computable, and sufficiently informative for the checkpoint tests.

Checkpoint 3 heuristic

heuristic1 must always return a valid cover and must run in polynomial time. It must also include a randomized component, perform multiple attempts or restarts, retain the best valid cover found so far, and reproduce the same result when run with the same --seed.

A single deterministic greedy construction followed immediately by return is not sufficient for heuristic1.

Course benchmark suites

The supplied MVC benchmark manifest is located at:

benchmarks/minimum_vertex_cover/manifest.json

Run the common experiment tool with, for example:

python tools/run_experiments.py --suite exact_frontier
python tools/run_experiments.py --suite quality_known
python tools/run_experiments.py --suite heuristic_scale
python tools/run_experiments.py --suite structure

Exact frontier

The exact-search frontier contains three known-optimum families:

balanced complete bipartite graphs;
disjoint star forests; and
disjoint triangles.

The default local exact-frontier timeout is 15 minutes per algorithm/instance. After one algorithm times out on a member of a frontier family, larger members of that same family are skipped for that algorithm. Gradescope uses shorter safety ceilings; the local frontier is where you study when each exact method becomes impractical.

Heuristic scale

The scale suite uses bipartite graphs with certified optima at 500, 2,000, and 5,000 vertices. In each graph, one side of the bipartition is a cover of size $k$ , while a matching of size $k$ proves that no smaller cover exists.

Structural experiment

The required structural family holds both size and optimum fixed:

$n=300$ ;
$OPT=120$ .

The amount of additional cross-edge structure is changed to produce sparse, medium, and dense instances. This lets you investigate the effect of edge density without simultaneously changing the number of vertices or the known optimal cover size.

See:

benchmarks/minimum_vertex_cover/structure.md

for the construction and interpretation details.