Certificates and Engineering Contracts

A returned number is an answer claim. A witness gives enough structure to inspect feasibility; a certificate may additionally establish optimality. Design outputs so a different implementation can check them without trusting the solver's trace.

A verification ladder

Result	Feasibility evidence	Additional optimality/completeness obligation
BFS/weighted distance	Parent edges form a contiguous source route with the reported cost	Correct distance proof or relaxation/layer certificate; one route alone only gives an upper bound
Topological order	Permutation of every vertex; every edge goes forward	Those checks fully establish this contract; cycle failure needs a separate argument/witness
SCC partition	Every vertex exactly once; members mutually reachable	Maximality: different groups are not mutually reachable; condensation is acyclic
Spanning forest	Correct component coverage, acyclicity, summed edge weights	Cut/exchange proof or non-tree-edge path maximum condition
Maximum flow	Capacities, conservation, matching terminal net values	Feasible source/sink cut of equal capacity
Maximum matching	Allowed pairs, distinct endpoints	Integral-flow optimum or another valid upper bound; maximality is insufficient

For finite shortest distances, a rigorous certificate can combine a source-zero potential d, edge inequalities d[v] <= d[u]+w on reachable edges, and tight parent paths reaching every claimed reachable vertex. Inequalities imply that d is no larger than any route cost; tight paths achieve d, giving equality. Claimed unreachable vertices need closure of the reachable set under outgoing edges. Handle unbounded regions separately; a negative cycle witness needs negative sum plus source-to-cycle and cycle-to-target reachability.

Semantic distinctions that prevent bugs

• Preserve original edge identities for parallel channels and path reconstruction.
• Distinguish nonexistent edges from zero-valued edges, and unreachable vertices from those whose cost is unbounded below.
• Define direction separately for routes, dependencies and undirected connection.
• Treat equal-cost witnesses as a set of valid answers unless deterministic tie order is explicitly part of the contract.
• For residual graphs, distinguish cancellation arcs from original antiparallel edges; capacity and flow are indexed by original records.
• A topological order specifies precedence. Durations, worker limits, failure handling and dynamic graph mutation require additional scheduling contracts.

What tests can and cannot establish

Small exhaustive tests can compare all three-vertex digraphs to a reachability oracle and all 3-by-3 bipartite graphs to matching enumeration. Forest subset and cut enumeration provide different algorithms for small-instance comparison. These are exponential oracles, not production alternatives. Agreement does not exclude shared mistakes; inspect hand-derived fixtures and deliberately corrupt witnesses to verify that the checkers actually reject them.

Mutation tests should include wrong numeric answers and plausible values paired with impossible witnesses. Checking only a scalar optimum misses conservation failures, lost multiplicity or paths using the wrong parallel edge. Conversely, requiring one exact tied optimum rejects correct implementations.

Costs and measurements

Count all declared vertices, input edge records, representation conversion and validation. Distinguish indexed and lazy heap state. SCC transpose storage is O(V+E); flow stores two residual arcs per original edge; those constant factors still matter to memory budgets. Big integers make arithmetic bit cost nonconstant. No elapsed-time ratio proves an asymptotic bound.

For an optional benchmark, record runtime/compiler, hardware, revision, input generator and seed, density, component structure, duplicate/loop policy, weight domain and bit width. State whether parsing, conversion, copies, validation and witness checking are timed. Retain repetitions, raw measurements and spread; verify results outside the timed region. Compare algorithms satisfying the same contract, not a value-only solver against a full-witness solver without accounting.

Transfer task

Take a graph result and change one assumption: a weight becomes negative, a task edge reverses meaning, a worker can take two jobs, or a cost-minimal network must survive one edge failure. State which old proof fails and produce a counterexample. Revise the model before modifying the code. The capstone uses this discipline.