Choose a solver without overstating guarantees
What this concept is
Choose among exact search, a proven approximation, a heuristic, a parameterized method or a restricted problem based on constraints and evidence. A restriction may make a hard general problem tractable; a heuristic alone does not provide an approximation ratio.
Why it matters here
Later software design must expose guarantees as part of an interface. A returned object should not conceal whether it is feasible, optimal, bounded, or unresolved.
Concrete example
For a returned cover of size 6 and matching of size 4, we know 4≤OPT≤6 and the returned cover is at most 1.5 times optimum. If exact search later finds size 5, the measured ratio becomes 6/5. The earlier certificate remains valid. A bound derived from one instance does not become a universal 1.5-approximation theorem.
Common confusion / misconception
An engineering timeout is not NP-hardness evidence. NP-hardness does not prohibit useful exact solvers on small or structured instances. Polynomial-time does not automatically mean practical at the required scale.
How to use it
Write a decision memo: graph model, objective, input limits, required guarantee, certificate verifier, rejected alternative and missing evidence. Preserve a lower bound alongside the feasible solution. If the graph is weighted or directed, stop and restate the problem before reusing the unweighted proof. Undecidability is a different issue: finite exhaustive vertex-cover search always terminates, unlike problems such as general program halting.
Check yourself
What should an API return when it has a feasible incumbent but has not proved optimality? Which fields keep that distinction visible?
Mini drill or application
For a star and a cycle, compare exact and approximate results, inspect the certificates, and defend which solver to expose under two different resource budgets. Use the lab report rather than invented timings.
Read this only if stuck
Use Erickson’s Algorithms and lecture notes for reductions and hardness, and the selective reading guide for the matching approximation. Full-book reading is not required.