Skip to main content

Solver-selection appendix

Reuse the lab as a separate semester-project appendix; the existing release planner does not need vertex-cover logic artificially inserted into it.

  1. State the graph and objective contract. Supply the reduction from Independent Set and the 3-SAT hardness chain, marking the external theorem used.
  2. Preserve exact and approximate outputs for the supplied fixtures and one changed graph. Independently verify each cover and matching. Explain when the lower bound certifies optimality and when it does not.
  3. Prove the approximation guarantee and account for normalization, enumeration, working memory and output cost. Include a weighted counterexample and a rejected over-limit exact request.
  4. Propose a result interface distinguishing feasible solution, lower bound, proven optimum and unresolved search. Do not label a teaching size rejection “infeasible.” Explain how an incumbent could still be useful after a budget interruption in a future solver.
  5. Defend a solver choice under a small exact-workload requirement and under a larger workload accepting a factor-two bound. State which new proof is needed if the objective changes to weighted cover.

Deliver code, run instructions, actual outputs, proof notes, source references and help record. Reproduce one changed case unaided. Reuse this appendix in S6 at semester review; it is counted within the module workload. No duplicate implementation or benchmark is required.