Reviewer calibration

CA1: cover budget gives a decision problem; a vertex set is a search witness; minimum cardinality is optimization. State vertex/edge encoding, membership cost and polynomial witness length. Verifier acceptance establishes only feasibility and the specified budget.

CA2: (G,k) maps to (G,n−k). Complements exchange independent sets and covers with reversed size inequalities. Preserve both implications. Reduce a known hard source to the target for hardness.

CA3: literal occurrences are distinct, clause vertices form cliques, contradictory literals receive cross edges. At most 3m vertices and O(m²) edges. A satisfying assignment yields one consistent occurrence per clause; an independent set of m yields a consistent partial assignment satisfying every clause. Use the known NP-completeness of 3-SAT explicitly. Cover also has a polynomial verifier.

CA4: any edge with two unselected endpoints contradicts maximality; each matching edge needs a different cover vertex; returned size is twice the matching size. A single weighted edge with costs 100 and 1 refutes weighted factor two. Maximum matching is stronger than needed.

CA5: inspect original code and retained output, including isolated vertices, duplicate/reversed edges, invalid endpoints, empty graph, loops and rejection above the exact guard. Tests must agree with an independent small-graph oracle. Never award independent competence for running reference code alone.

CA6: bounds L≤OPT≤U justify an instance ratio U/L only for L>0; handle zero-edge cases separately. Interrupted search does not prove no. Branching on an uncovered edge is complete because at least one endpoint must be selected, and decreasing k bounds depth; this is exponential in k, not polynomial in all inputs.