Practice calibration

1. The center alone is an optimal cover; any one edge supplies lower bound one. The approximation can return the center and one leaf, size two.
2. Map (G,k) to (G,n−k), using the complement of a vertex set, not the graph complement. A solver for the target cover problem solves the source independent-set problem. State the restricted threshold domain or handle trivial thresholds separately.
3. Two triangles plus edges between a and ¬a, and b and ¬b. Choose c from the first and d from the second; the remaining four occurrence vertices form a cover. Occurrences are distinct vertices even when literals repeat.
4. Substitution gives n2^b operations. Finite subset enumeration still terminates for cover; hard is not the same as uncomputable.
5. An uncovered edge could have been added to the matching, contradicting maximality. Disjoint matching edges require distinct covering vertices. A star achieves ratio two; a single edge with weights 100 and 1 defeats the unweighted rule for weighted cost.
6. 5≤OPT≤8, so the returned solution costs at most 8/5 times OPT. Interrupted search does not establish an optimum or a no-instance. Preserve the incumbent and proven lower bound separately.

Entry calibration

For vertices A,B,C and edges AB,BC, the middle vertex B touches both edges. The subsets are empty; A, B, C; AB, AC, BC; ABC. A checker scans the edges against a supplied set, while exhaustive search considers candidates until its stopping rule is met. Checking one candidate does not prove it is minimum. Change to a triangle and repeat: no single vertex touches all three edges, but any pair does. This is prerequisite graph/set reasoning, not a requirement to know NP-completeness before the module.