{"id":"network-cut-capacity-check","version":"1.0.0","description":"Check a claimed s-t cut: source-side membership, the edges crossing it and its capacity, with exact integers.","supported_operations":["check the capacity of an s-t cut","verify which edges cross a cut","validate a claimed minimum cut partition","is the source on the source side of this cut","sum capacities of edges leaving a vertex set claim","audit a cut certificate in a flow network"],"unsupported_operations":["finding a minimum cut (use maximum-flow-certificate-check to verify one)","undirected or global (non s-t) minimum cuts","vertex capacities or weighted vertex cuts","counting edges in the reverse direction toward the capacity"],"semantics":["Reference: CLRS 4th ed. (2022) section 24.2, cut (S, T) of a flow network with s in S and t in T = V - S, capacity c(S, T) = sum of c(u, v) over edges from S to T only; reference_version is returned with every result.","Network rules as in network-flow-feasibility-check: unique string node ids compared exactly, directed edges identified by array index, parallel edges each counted, integers exact (JSON safe integer or canonical string of at most 30 digits).","claim.source_side lists the node ids of S; claim.capacity is the claimed c(S, T); claim.crossing_edges (optional) lists the indices of the edges from S to T, in any order.","Check order: source_side in list order (unknown_node, duplicate_node, with position), then source_not_in_source_side, sink_in_source_side; then crossing_edges in list order (unknown_edge for an index out of range, duplicate_edge); then edges by index (crossing_edge_missing for an S-to-T edge not listed, crossing_edge_extra for a listed edge that does not go from S to T); then capacity_mismatch.","Edges from T to S never count toward the capacity. cut_capacity is the exact c(S, T) when the source side is valid, 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":["source_side","capacity"],"properties":{"source_side":{"type":"array","maxItems":2000,"items":{"type":"string","minLength":1,"maxLength":64}},"capacity":{"anyOf":[{"type":"integer","minimum":0},{"type":"string","minLength":1,"maxLength":30,"pattern":"^(0|[1-9][0-9]*)$"}]},"crossing_edges":{"type":"array","maxItems":10000,"items":{"type":"integer","minimum":0}}}}}},"output_schema":{"type":"object","additionalProperties":false,"required":["valid","reason","first_discrepancy","cut_capacity","reference_version"],"properties":{"valid":{"type":"boolean"},"reason":{"type":["string","null"],"enum":[null,"unknown_node","duplicate_node","source_not_in_source_side","sink_in_source_side","unknown_edge","duplicate_edge","crossing_edge_missing","crossing_edge_extra","capacity_mismatch"]},"first_discrepancy":{"type":["object","null"],"additionalProperties":false,"required":["kind"],"properties":{"kind":{"type":"string","enum":["cut","edge","value"]},"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"}}},"cut_capacity":{"type":["string","null"]},"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":{"source_side":["s","v1","v2"],"capacity":26,"crossing_edges":[3,5]}},"output":{"valid":true,"reason":null,"first_discrepancy":null,"cut_capacity":"26","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":{"source_side":["s","v1","v2"],"capacity":35}},"output":{"valid":false,"reason":"capacity_mismatch","first_discrepancy":{"kind":"value","claimed":"35","actual":"26"},"cut_capacity":"26","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/network-cut-capacity-check/versions/1.0.0/execute"}