{"id":"maxflow-certificate-check","version":"1.0.0","description":"Check an exact max-flow/min-cut certificate and return the first deterministic discrepancy.","supported_operations":["check max flow certificate","validate max flow min cut proof","check claimed maximum flow","verify minimum cut witness","audit flow optimality certificate","find first maxflow certificate discrepancy"],"unsupported_operations":["compute a maximum flow","choose or repair a cut partition"],"semantics":["The claimed flow is checked for feasibility first, then source value, then source-side membership, cut capacity, and crossing-edge equality conditions.","source_side is an unordered duplicate-free list naming the cut side containing source and excluding sink; omitted nodes are on the sink side.","Cut capacity sums original capacities of edges directed from source_side to its complement; parallel edges count separately.","All numeric fields are canonical nonnegative decimal strings and arithmetic is exact.","By max-flow/min-cut equality, a feasible flow whose value equals this cut capacity is maximum and the cut is minimum.","Reference version: Ford-Fulkerson max-flow/min-cut theorem (Ahuja-Magnanti-Orlin 1993, Sections 6.1-6.5)."],"limits":{"max_nodes":256,"max_edges":4096,"max_integer_digits":78,"max_node_id_bytes":64},"pricing":{"status":"unpriced","charge_usd":null},"input_schema":{"type":"object","additionalProperties":false,"required":["nodes","edges","source","sink","flow","claimed_value","source_side"],"properties":{"nodes":{"type":"array","minItems":2,"maxItems":256,"uniqueItems":true,"items":{"type":"string","minLength":1,"maxLength":64}},"edges":{"type":"array","maxItems":4096,"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":{"type":"string","minLength":1,"maxLength":78,"pattern":"^(0|[1-9][0-9]*)$"}}}},"source":{"type":"string","minLength":1,"maxLength":64},"sink":{"type":"string","minLength":1,"maxLength":64},"flow":{"type":"array","maxItems":4096,"items":{"type":"string","minLength":1,"maxLength":78,"pattern":"^(0|[1-9][0-9]*)$"}},"claimed_value":{"type":"string","minLength":1,"maxLength":78,"pattern":"^(0|[1-9][0-9]*)$"},"source_side":{"type":"array","minItems":1,"maxItems":256,"uniqueItems":true,"items":{"type":"string","minLength":1,"maxLength":64}}}},"output_schema":{"type":"object","additionalProperties":false,"required":["valid","reason","discrepancy","reference_version"],"properties":{"valid":{"type":"boolean"},"reason":{"type":["string","null"]},"discrepancy":{"anyOf":[{"type":"null"},{"type":"object","additionalProperties":false,"required":["path","expected","actual"],"properties":{"path":{"type":"string"},"expected":{"type":["string","null"]},"actual":{"type":["string","null"]}}}]},"reference_version":{"type":"string","const":"Ford-Fulkerson max-flow/min-cut theorem (Ahuja-Magnanti-Orlin 1993, Sections 6.1-6.5)"}}},"examples":[{"input":{"nodes":["s","t"],"edges":[{"from":"s","to":"t","capacity":"3"}],"source":"s","sink":"t","flow":["3"],"claimed_value":"3","source_side":["s"]},"output":{"valid":true,"reason":null,"discrepancy":null,"reference_version":"Ford-Fulkerson max-flow/min-cut theorem (Ahuja-Magnanti-Orlin 1993, Sections 6.1-6.5)"}},{"input":{"nodes":["s","t"],"edges":[{"from":"s","to":"t","capacity":"3"}],"source":"s","sink":"t","flow":["2"],"claimed_value":"2","source_side":["s"]},"output":{"valid":false,"reason":"cut_capacity_mismatch","discrepancy":{"path":"source_side","expected":"3","actual":"2"},"reference_version":"Ford-Fulkerson max-flow/min-cut theorem (Ahuja-Magnanti-Orlin 1993, Sections 6.1-6.5)"}}],"execute_url":"/v1/tools/maxflow-certificate-check/versions/1.0.0/execute"}