{"id":"minimum-spanning-tree-certificate-check","version":"1.0.0","description":"Check a claimed minimum spanning tree: structure, exact weight, then the cycle/cut optimality test with a swap witness","supported_operations":["verify minimum spanning tree","check mst optimality","is this the minimum spanning tree","mst cycle property check","mst cut property certificate","find cheaper swap for spanning tree","validate kruskal or prim result"],"unsupported_operations":["computing a minimum spanning tree from scratch","minimum spanning forests of disconnected graphs","directed minimum arborescences (Chu-Liu/Edmonds)","bottleneck or degree-constrained spanning trees"],"semantics":["Order: structural stage (missing_edge, duplicate_edge, cycle_edge with a cycle witness, disconnected) in tree_edge_ids order; then, when claimed_weight is not null, the exact tree weight must equal it (weight_mismatch); then the cycle condition over non-tree edges in graph.edges order.","Cycle condition: for every non-tree edge e = {u, v} with u != v, w(e) must be at least the heaviest weight on the unique tree path from u to v; the first failure is cycle_property_violated with index = position in graph.edges, expected = heaviest tree-path weight, actual = w(e), witness_edge_ids = the tree path from u to v.","The condition holds for all non-tree edges exactly when the tree is a minimum spanning tree (cycle property, equivalently each tree edge is light for its fundamental cut, CLRS Theorem 21.1). Swapping e for the first heaviest witness edge lowers the weight. Ties are allowed, so every alternative minimum tree passes.","claimed_weight is a canonical integer string of at most 40 digits or null (no weight claim); tree_weight is the computed sum when the structure is valid, otherwise null. Arithmetic is exact.","Undirected edges {id, u, v, weight}; parallel edges and self-loops allowed (non-tree self-loops never violate the condition); IDs compared code unit for code unit. Graph errors throw invalid_input; size limits throw limit_exceeded first.","Reference: CLRS 4th ed. (2022) chapter 21; reference_version \"clrs-4e-2022-ch21-minimum-spanning-trees\"."],"limits":{"max_vertices":500,"max_edges":2000,"max_tree_edges":2000,"max_id_bytes":64,"max_integer_digits":40},"pricing":{"status":"unpriced","charge_usd":null},"input_schema":{"type":"object","additionalProperties":false,"required":["graph","tree_edge_ids","claimed_weight"],"properties":{"graph":{"type":"object","additionalProperties":false,"required":["vertices","edges"],"properties":{"vertices":{"type":"array","minItems":1,"maxItems":500,"items":{"type":"string","minLength":1,"maxLength":64}},"edges":{"type":"array","maxItems":2000,"items":{"type":"object","additionalProperties":false,"required":["id","u","v","weight"],"properties":{"id":{"type":"string","minLength":1,"maxLength":64},"u":{"type":"string","minLength":1,"maxLength":64},"v":{"type":"string","minLength":1,"maxLength":64},"weight":{"type":"string","pattern":"^(0|-?[1-9][0-9]*)$"}}}}}},"tree_edge_ids":{"type":"array","maxItems":2000,"items":{"type":"string","minLength":1,"maxLength":64}},"claimed_weight":{"type":["string","null"],"pattern":"^(0|-?[1-9][0-9]*)$"}}},"output_schema":{"type":"object","additionalProperties":false,"required":["valid","reason","first_discrepancy","tree_weight","reference_version"],"properties":{"valid":{"type":"boolean"},"reason":{"type":["string","null"],"enum":[null,"missing_edge","duplicate_edge","cycle_edge","disconnected","weight_mismatch","cycle_property_violated"]},"first_discrepancy":{"type":["object","null"],"additionalProperties":false,"required":["field","index","vertex","edge_id","expected","actual","witness_edge_ids"],"properties":{"field":{"type":"string","enum":["tree_edge_ids","graph.vertices","claimed_weight","graph.edges"]},"index":{"type":["integer","null"],"minimum":0},"vertex":{"type":["string","null"]},"edge_id":{"type":["string","null"]},"expected":{"type":["string","null"]},"actual":{"type":["string","null"]},"witness_edge_ids":{"type":["array","null"],"maxItems":500,"items":{"type":"string","minLength":1,"maxLength":64}}}},"tree_weight":{"type":["string","null"],"pattern":"^(0|-?[1-9][0-9]*)$"},"reference_version":{"type":"string","const":"clrs-4e-2022-ch21-minimum-spanning-trees"}}},"examples":[{"input":{"graph":{"vertices":["a","b","c","d"],"edges":[{"id":"ab","u":"a","v":"b","weight":"1"},{"id":"bc","u":"b","v":"c","weight":"2"},{"id":"cd","u":"c","v":"d","weight":"3"},{"id":"da","u":"d","v":"a","weight":"4"},{"id":"ac","u":"a","v":"c","weight":"5"}]},"tree_edge_ids":["ab","bc","cd"],"claimed_weight":"6"},"output":{"valid":true,"reason":null,"first_discrepancy":null,"tree_weight":"6","reference_version":"clrs-4e-2022-ch21-minimum-spanning-trees"}},{"input":{"graph":{"vertices":["a","b","c","d"],"edges":[{"id":"ab","u":"a","v":"b","weight":"1"},{"id":"bc","u":"b","v":"c","weight":"2"},{"id":"cd","u":"c","v":"d","weight":"3"},{"id":"da","u":"d","v":"a","weight":"4"},{"id":"ac","u":"a","v":"c","weight":"5"}]},"tree_edge_ids":["ab","bc","da"],"claimed_weight":"7"},"output":{"valid":false,"reason":"cycle_property_violated","first_discrepancy":{"field":"graph.edges","index":2,"vertex":null,"edge_id":"cd","expected":"4","actual":"3","witness_edge_ids":["bc","ab","da"]},"tree_weight":"7","reference_version":"clrs-4e-2022-ch21-minimum-spanning-trees"}}],"execute_url":"/v1/tools/minimum-spanning-tree-certificate-check/versions/1.0.0/execute"}