{"abstract":"Matching freezes an early choice instead of following an augmenting path.","category":"Graph algorithm invariants","checks":8,"contract":"Return maximum matching cardinality for the given ordered distinct left vertices and bipartite edges (left label, right label). The two sides are separate namespaces; repeated edges count once.","contract_signature":"left, edges","evaluation_group":"model-8d8a5d457b9e362a","failed_approach":"Keeping the visited set across augmentations blocks valid later searches through previously examined vertices.","family":"z-graphs-matching-augmenting-reset","id":"FA-11716","implementations":{"attempt":{"sha256":"f1558a5e10aa0223515678fbf509613909e44137ca461ea330430951cc99a990","source":"\"\"\"Failure Map reference implementation. Python standard library only.\"\"\"\nimport json\nfrom itertools import combinations\nN = 1\nobservations = []\ndef solve(left, edges):\n    adj = {u:[] for u in left}\n    for u,v in edges:\n        if v not in adj[u]: adj[u].append(v)\n    match = {}\n    visited = set()\n    \n    def augment(u, seen):\n        for v in adj[u]:\n            if v in seen: continue\n            seen.add(v)\n            if v not in match or augment(match[v], seen):\n                match[v] = u\n                return True\n        return False\n    for u in left:\n        augment(u, visited)\n    return len(match)\ndef check(label, actual, expected):\n    observations.append({\"check\": label, \"actual\": actual, \"expected\": expected, \"passed\": actual == expected})\na,b,c = N,N+1,N+2\ncheck('displace first match', solve([a,b], [(a,0),(a,1),(b,0)]), 2)\ncheck('long augmenting chain', solve([a,b,c], [(a,0),(a,1),(b,1),(b,2),(c,0)]), 3)\ncheck('empty', solve([], []), 0)\ncheck('unmatched left vertex', solve([a,b], [(b,0)]), 1)\ncheck('same right bottleneck', solve([a,b], [(a,0),(b,0)]), 1)\ncheck('duplicate edge', solve([a], [(a,0),(a,0)]), 1)\ncheck('side namespaces may share labels', solve([a,b], [(a,a),(b,b)]), 2)\ncheck('variable-size independent matching', solve(list(range(N)), [(i,i) for i in range(N)]), N)\nprint(json.dumps({\"observations\": observations, \"passed\": all(x[\"passed\"] for x in observations)}, ensure_ascii=False))\nraise SystemExit(0 if all(x[\"passed\"] for x in observations) else 1)\n"},"broken":{"sha256":"ece127ccbe21a69ecaa26ed9ef656b6b5f6414906ddc775c248729513b4ce361","source":"\"\"\"Failure Map reference implementation. Python standard library only.\"\"\"\nimport json\nfrom itertools import combinations\nN = 1\nobservations = []\ndef solve(left, edges):\n    adj = {u:[] for u in left}\n    for u,v in edges:\n        if v not in adj[u]: adj[u].append(v)\n    match = {}\n    pass\n    \n    def augment(u, seen):\n        for v in adj[u]:\n            if v in seen: continue\n            seen.add(v)\n            if v not in match or False:\n                match[v] = u\n                return True\n        return False\n    for u in left:\n        augment(u, set())\n    return len(match)\ndef check(label, actual, expected):\n    observations.append({\"check\": label, \"actual\": actual, \"expected\": expected, \"passed\": actual == expected})\na,b,c = N,N+1,N+2\ncheck('displace first match', solve([a,b], [(a,0),(a,1),(b,0)]), 2)\ncheck('long augmenting chain', solve([a,b,c], [(a,0),(a,1),(b,1),(b,2),(c,0)]), 3)\ncheck('empty', solve([], []), 0)\ncheck('unmatched left vertex', solve([a,b], [(b,0)]), 1)\ncheck('same right bottleneck', solve([a,b], [(a,0),(b,0)]), 1)\ncheck('duplicate edge', solve([a], [(a,0),(a,0)]), 1)\ncheck('side namespaces may share labels', solve([a,b], [(a,a),(b,b)]), 2)\ncheck('variable-size independent matching', solve(list(range(N)), [(i,i) for i in range(N)]), N)\nprint(json.dumps({\"observations\": observations, \"passed\": all(x[\"passed\"] for x in observations)}, ensure_ascii=False))\nraise SystemExit(0 if all(x[\"passed\"] for x in observations) else 1)\n"}},"limitations":"Small explicit graphs only; exhaustive reference algorithms emphasize semantics rather than asymptotic performance. This reproducer isolates one failure mechanism. Results cover the supplied fixtures. Variants within a family share a test contract and should remain grouped when constructing evaluation splits. Related mechanisms with a shared evaluation_group must also remain together; these controlled models are not independent production incidents.","method":"Deterministic executable model with adversarial boundary fixtures.","provenance":{"created_by":"Failure Map","dependencies":"Python standard library","family":"z-graphs-matching-augmenting-reset","generated_at":"2026-09-29T14:38:50.438472+00:00","license":"CC0-1.0","python":"3.12.14","seed":1,"split":"open-access"},"relevance":"A deterministic in-memory graph model isolates this invariant; no large-graph performance or production graph engine behavior is claimed.","root_cause":"A greedy edge selection cannot displace earlier matches to expose a larger matching.","sha256":"b9fb442d8a49d259cfb3f080d88aa9097a3ece5cdc8b2931fde90d5aaa7daa24","title":"Matching freezes an early choice instead of following an augmenting path · case 01","variant":1,"variant_policy":"Five numbered records share a model and may reuse boundary fixtures.","verified":true,"visibility":"public","verification":{"attempt":{"elapsed_ms":39.612,"exit_code":1,"observations":[{"actual":1,"check":"displace first match","expected":2,"passed":false},{"actual":2,"check":"long augmenting chain","expected":3,"passed":false},{"actual":0,"check":"empty","expected":0,"passed":true},{"actual":1,"check":"unmatched left vertex","expected":1,"passed":true},{"actual":1,"check":"same right bottleneck","expected":1,"passed":true},{"actual":1,"check":"duplicate edge","expected":1,"passed":true},{"actual":2,"check":"side namespaces may share labels","expected":2,"passed":true},{"actual":1,"check":"variable-size independent matching","expected":1,"passed":true}],"passed":false,"stderr":"","stdout":"{\"observations\": [{\"check\": \"displace first match\", \"actual\": 1, \"expected\": 2, \"passed\": false}, {\"check\": \"long augmenting chain\", \"actual\": 2, \"expected\": 3, \"passed\": false}, {\"check\": \"empty\", \"actual\": 0, \"expected\": 0, \"passed\": true}, {\"check\": \"unmatched left vertex\", \"actual\": 1, \"expected\": 1, \"passed\": true}, {\"check\": \"same right bottleneck\", \"actual\": 1, \"expected\": 1, \"passed\": true}, {\"check\": \"duplicate edge\", \"actual\": 1, \"expected\": 1, \"passed\": true}, {\"check\": \"side namespaces may share labels\", \"actual\": 2, \"expected\": 2, \"passed\": true}, {\"check\": \"variable-size independent matching\", \"actual\": 1, \"expected\": 1, \"passed\": true}], \"passed\": false}\n"},"broken":{"elapsed_ms":38.867,"exit_code":1,"observations":[{"actual":1,"check":"displace first match","expected":2,"passed":false},{"actual":2,"check":"long augmenting chain","expected":3,"passed":false},{"actual":0,"check":"empty","expected":0,"passed":true},{"actual":1,"check":"unmatched left vertex","expected":1,"passed":true},{"actual":1,"check":"same right bottleneck","expected":1,"passed":true},{"actual":1,"check":"duplicate edge","expected":1,"passed":true},{"actual":2,"check":"side namespaces may share labels","expected":2,"passed":true},{"actual":1,"check":"variable-size independent matching","expected":1,"passed":true}],"passed":false,"stderr":"","stdout":"{\"observations\": [{\"check\": \"displace first match\", \"actual\": 1, \"expected\": 2, \"passed\": false}, {\"check\": \"long augmenting chain\", \"actual\": 2, \"expected\": 3, \"passed\": false}, {\"check\": \"empty\", \"actual\": 0, \"expected\": 0, \"passed\": true}, {\"check\": \"unmatched left vertex\", \"actual\": 1, \"expected\": 1, \"passed\": true}, {\"check\": \"same right bottleneck\", \"actual\": 1, \"expected\": 1, \"passed\": true}, {\"check\": \"duplicate edge\", \"actual\": 1, \"expected\": 1, \"passed\": true}, {\"check\": \"side namespaces may share labels\", \"actual\": 2, \"expected\": 2, \"passed\": true}, {\"check\": \"variable-size independent matching\", \"actual\": 1, \"expected\": 1, \"passed\": true}], \"passed\": false}\n"}},"member_only":{"stages":["fixed"],"fields":["implementations.fixed","verification.fixed","harness","repair"],"note":"The verified repair, its recorded checks, the repair description, and the scoring harness are available to members."}}