Exact and approximate cover lab

Download the lab archive. Extract it, open complexity-approximation, and use Python 3.10+ with its standard library. Windows users may substitute py -3 for python3.

python3 check.py starter

An initial NotImplementedError is intentional. Implement the three contracts: cover verification, exact minimum cover by size-ordered enumeration, and the maximal-matching approximation. Keep the provided graph normalizer; understand its handling of isolated vertices, duplicate/reversed edges, and rejected loops.

python3 run.py starter > results.json

Before running, predict the optimum and matching lower bound for the triangle, star and cycle. Compare your predictions with retained output. Independently inspect every certificate; a verifier that always returns true is not evidence. Change the graph and vertex labeling, then repeat. Output ratios describe these instances; the factor-two proof must stand independently.

After an attempt, run python3 check.py reference and compare code. Public checks enumerate all simple graphs through five vertices with a separate independent-set oracle. They also check graph validation, witness structure, duplicate normalization and the exact-size guard. The exact algorithm rejects n>12 rather than quietly returning an approximate answer. A size-12 admission limit is for this teaching implementation, not a universal runtime promise.

Complete the project appendix using these same files. Lab and project together take an estimated 8–11 hours. Keep raw outputs, a repaired mistake and assistance declarations. Passing reference checks is setup evidence, not learner completion.