{"id":"maximum-flow-certificate-check","version":"1.0.0","description":"Check a claimed max flow with a min-cut certificate or residual search; reports the first failure or augmenting path.","supported_operations":["verify a maximum flow answer","check max flow with a min cut certificate","is this flow maximum or is there an augmenting path","validate claimed max flow value of a network","certify max-flow min-cut duality for a solution","find an augmenting path that disproves a max flow claim"],"unsupported_operations":["computing a maximum flow from scratch without a claimed flow","minimum-cost or multi-commodity flows","real-valued capacities (exact integers only)","listing every minimum cut"],"semantics":["Reference: CLRS 4th ed. (2022) sections 24.1-24.2: a flow f is maximum iff its residual network has no augmenting path iff |f| = c(S, T) for some cut (max-flow min-cut theorem); reference_version is returned with every result.","Network and integer rules as in network-flow-feasibility-check. claim.flows (one per edge, edge order) and claim.value are required; claim.source_side (optional) is a cut certificate.","Check order: feasibility exactly as network-flow-feasibility-check (flow_length_mismatch, negative_flow, capacity_exceeded, conservation_violated), then claim.value against the flow value (value_mismatch).","With claim.source_side (method cut_certificate): source-side checks as in network-cut-capacity-check (unknown_node, duplicate_node, source_not_in_source_side, sink_in_source_side), then edges by index: an S-to-T edge below capacity is cut_edge_not_saturated, a T-to-S edge with positive flow is backward_edge_has_flow. Passing all checks proves |f| = c(S, T), so f is maximum and (S, T) is a minimum cut.","Without claim.source_side (method residual_search): breadth-first search from the source in the residual network, dequeuing nodes first-in first-out and scanning each node's incident edges once in edge index order (forward residual when the edge leaves the node with flow < capacity, backward residual when it enters with flow > 0; self-loops skipped). Reaching the sink gives reason augmenting_path with path (edge_index, direction), path_nodes and residual_capacity (the bottleneck).","flow_value is the exact flow value whenever the flow is feasible, else null."],"limits":{"max_nodes":2000,"max_edges":10000,"max_id_chars":64,"max_integer_digits":30},"pricing":{"status":"unpriced","charge_usd":null},"input_schema":{"type":"object","additionalProperties":false,"required":["nodes","edges","source","sink","claim"],"properties":{"nodes":{"type":"array","minItems":2,"maxItems":2000,"items":{"type":"string","minLength":1,"maxLength":64}},"edges":{"type":"array","maxItems":10000,"items":{"type":"object","additionalProperties":false,"required":["from","to","capacity"],"properties":{"from":{"type":"string","minLength":1,"maxLength":64},"to":{"type":"string","minLength":1,"maxLength":64},"capacity":{"anyOf":[{"type":"integer","minimum":0},{"type":"string","minLength":1,"maxLength":30,"pattern":"^(0|[1-9][0-9]*)$"}]}}}},"source":{"type":"string","minLength":1,"maxLength":64},"sink":{"type":"string","minLength":1,"maxLength":64},"claim":{"type":"object","additionalProperties":false,"required":["flows","value"],"properties":{"flows":{"type":"array","maxItems":10000,"items":{"anyOf":[{"type":"integer"},{"type":"string","minLength":1,"maxLength":31,"pattern":"^(0|-?[1-9][0-9]*)$"}]}},"value":{"anyOf":[{"type":"integer"},{"type":"string","minLength":1,"maxLength":31,"pattern":"^(0|-?[1-9][0-9]*)$"}]},"source_side":{"type":"array","maxItems":2000,"items":{"type":"string","minLength":1,"maxLength":64}}}}}},"output_schema":{"type":"object","additionalProperties":false,"required":["valid","reason","first_discrepancy","flow_value","method","reference_version"],"properties":{"valid":{"type":"boolean"},"reason":{"type":["string","null"],"enum":[null,"flow_length_mismatch","negative_flow","capacity_exceeded","conservation_violated","value_mismatch","unknown_node","duplicate_node","source_not_in_source_side","sink_in_source_side","cut_edge_not_saturated","backward_edge_has_flow","augmenting_path"]},"first_discrepancy":{"type":["object","null"],"additionalProperties":false,"required":["kind"],"properties":{"kind":{"type":"string","enum":["claim","edge","node","value","cut","path"]},"edge_index":{"type":"integer","minimum":0},"from":{"type":"string"},"to":{"type":"string"},"node":{"type":"string"},"position":{"type":"integer","minimum":0},"flow":{"type":"string"},"capacity":{"type":"string"},"inflow":{"type":"string"},"outflow":{"type":"string"},"claimed":{"type":"string"},"actual":{"type":"string"},"path":{"type":"array","maxItems":2000,"items":{"type":"object","additionalProperties":false,"required":["edge_index","direction"],"properties":{"edge_index":{"type":"integer","minimum":0},"direction":{"type":"string","enum":["forward","backward"]}}}},"path_nodes":{"type":"array","maxItems":2001,"items":{"type":"string"}},"residual_capacity":{"type":"string"}}},"flow_value":{"type":["string","null"]},"method":{"type":"string","enum":["cut_certificate","residual_search"]},"reference_version":{"type":"string"}}},"examples":[{"input":{"nodes":["s","v1","v2","v3","v4","t"],"edges":[{"from":"s","to":"v1","capacity":16},{"from":"s","to":"v2","capacity":13},{"from":"v2","to":"v1","capacity":4},{"from":"v1","to":"v3","capacity":12},{"from":"v3","to":"v2","capacity":9},{"from":"v2","to":"v4","capacity":14},{"from":"v4","to":"v3","capacity":7},{"from":"v3","to":"t","capacity":20},{"from":"v4","to":"t","capacity":4}],"source":"s","sink":"t","claim":{"flows":[11,12,1,12,0,11,7,19,4],"value":23,"source_side":["s","v1","v2","v4"]}},"output":{"valid":true,"reason":null,"first_discrepancy":null,"flow_value":"23","method":"cut_certificate","reference_version":"CLRS 4th ed. (2022) ch. 24 Maximum Flow: flow networks, cuts, residual networks, max-flow min-cut theorem; r55-flow-certificate-verifiers@1.0.0"}},{"input":{"nodes":["s","v1","v2","v3","v4","t"],"edges":[{"from":"s","to":"v1","capacity":16},{"from":"s","to":"v2","capacity":13},{"from":"v2","to":"v1","capacity":4},{"from":"v1","to":"v3","capacity":12},{"from":"v3","to":"v2","capacity":9},{"from":"v2","to":"v4","capacity":14},{"from":"v4","to":"v3","capacity":7},{"from":"v3","to":"t","capacity":20},{"from":"v4","to":"t","capacity":4}],"source":"s","sink":"t","claim":{"flows":[11,8,1,12,4,11,7,15,4],"value":19}},"output":{"valid":false,"reason":"augmenting_path","first_discrepancy":{"kind":"path","path":[{"edge_index":1,"direction":"forward"},{"edge_index":4,"direction":"backward"},{"edge_index":7,"direction":"forward"}],"path_nodes":["s","v2","v3","t"],"residual_capacity":"4"},"flow_value":"19","method":"residual_search","reference_version":"CLRS 4th ed. (2022) ch. 24 Maximum Flow: flow networks, cuts, residual networks, max-flow min-cut theorem; r55-flow-certificate-verifiers@1.0.0"}}],"execute_url":"/v1/tools/maximum-flow-certificate-check/versions/1.0.0/execute"}