{"abstract":"Transitive reduction lets the candidate edge justify its own removal.","category":"Graph algorithm invariants","checks":8,"contract":"For a directed acyclic graph, return sorted distinct edges of its transitive reduction as two-element lists. Remove an edge exactly when an alternative directed path joins its endpoints. Inputs are guaranteed acyclic.","contract_signature":"vertices, edges","evaluation_group":"model-9c8acdcdf3440fdd","failed_approach":"Checking only paths of at most two hops retains edges implied by longer paths.","family":"z-graphs-reduction-alternative-path","id":"FA-11721","implementations":{"attempt":{"sha256":"73d8d407ba544f6a9ffac34a1957ef65052d11fc1c5b8c9272f5de78230e92e2","source":"\"\"\"Failure Map reference implementation. Python standard library only.\"\"\"\nimport json\nfrom itertools import combinations\nN = 1\nobservations = []\ndef solve(vertices, edges):\n    unique = sorted(set(edges))\n    answer = []\n    for edge in unique:\n        u,v = edge\n        adj = {x:set() for x in vertices}\n        for a,b in unique:\n            if (a,b) == edge: continue\n            adj[a].add(b)\n        seen, todo = {u}, [u]\n        while todo:\n            x = todo.pop()\n            for y in adj[x] - seen:\n                seen.add(y)\n                if x == u: todo.append(y)\n        if v not in seen: answer.append([u,v])\n    return answer\ndef check(label, actual, expected):\n    observations.append({\"check\": label, \"actual\": actual, \"expected\": expected, \"passed\": actual == expected})\na,b,c,d = [10*N+i for i in range(4)]\ncheck('long alternate path', solve([a,b,c,d], [(a,b),(b,c),(c,d),(a,d)]), [[a,b],[b,c],[c,d]])\ncheck('single necessary edge', solve([a,b], [(a,b)]), [[a,b]])\ncheck('short alternate path', solve([a,b,c], [(a,b),(b,c),(a,c)]), [[a,b],[b,c]])\ncheck('empty', solve([], []), [])\ncheck('isolated nodes', solve([a,b], []), [])\ncheck('duplicate declaration', solve([a,b], [(a,b),(a,b)]), [[a,b]])\ncheck('fork has no redundancy', solve([a,b,c], [(a,b),(a,c)]), [[a,b],[a,c]])\ncheck('variable-length shortcut', solve(list(range(N+3)), [(i,i+1) for i in range(N+2)] + [(0,N+2)]), [[i,i+1] for i in range(N+2)])\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":"673135f98a402048447ed3f259324c4c7c91895c02920a2196c192b5f3a6c63a","source":"\"\"\"Failure Map reference implementation. Python standard library only.\"\"\"\nimport json\nfrom itertools import combinations\nN = 1\nobservations = []\ndef solve(vertices, edges):\n    unique = sorted(set(edges))\n    answer = []\n    for edge in unique:\n        u,v = edge\n        adj = {x:set() for x in vertices}\n        for a,b in unique:\n            if False: continue\n            adj[a].add(b)\n        seen, todo = {u}, [u]\n        while todo:\n            x = todo.pop()\n            for y in adj[x] - seen:\n                seen.add(y)\n                todo.append(y)\n        if v not in seen: answer.append([u,v])\n    return answer\ndef check(label, actual, expected):\n    observations.append({\"check\": label, \"actual\": actual, \"expected\": expected, \"passed\": actual == expected})\na,b,c,d = [10*N+i for i in range(4)]\ncheck('long alternate path', solve([a,b,c,d], [(a,b),(b,c),(c,d),(a,d)]), [[a,b],[b,c],[c,d]])\ncheck('single necessary edge', solve([a,b], [(a,b)]), [[a,b]])\ncheck('short alternate path', solve([a,b,c], [(a,b),(b,c),(a,c)]), [[a,b],[b,c]])\ncheck('empty', solve([], []), [])\ncheck('isolated nodes', solve([a,b], []), [])\ncheck('duplicate declaration', solve([a,b], [(a,b),(a,b)]), [[a,b]])\ncheck('fork has no redundancy', solve([a,b,c], [(a,b),(a,c)]), [[a,b],[a,c]])\ncheck('variable-length shortcut', solve(list(range(N+3)), [(i,i+1) for i in range(N+2)] + [(0,N+2)]), [[i,i+1] for i in range(N+2)])\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-reduction-alternative-path","generated_at":"2026-09-29T14:38:50.440522+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 reachability query includes the very edge being tested for redundancy.","sha256":"df7a32a3882f036b7a4a4646cc26764a9720c6dac9e00d92412d93fcaf5b4e91","title":"Transitive reduction lets the candidate edge justify its own removal · 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":37.936,"exit_code":1,"observations":[{"actual":[[10,11],[10,13],[11,12],[12,13]],"check":"long alternate path","expected":[[10,11],[11,12],[12,13]],"passed":false},{"actual":[[10,11]],"check":"single necessary edge","expected":[[10,11]],"passed":true},{"actual":[[10,11],[11,12]],"check":"short alternate path","expected":[[10,11],[11,12]],"passed":true},{"actual":[],"check":"empty","expected":[],"passed":true},{"actual":[],"check":"isolated nodes","expected":[],"passed":true},{"actual":[[10,11]],"check":"duplicate declaration","expected":[[10,11]],"passed":true},{"actual":[[10,11],[10,12]],"check":"fork has no redundancy","expected":[[10,11],[10,12]],"passed":true},{"actual":[[0,1],[0,3],[1,2],[2,3]],"check":"variable-length shortcut","expected":[[0,1],[1,2],[2,3]],"passed":false}],"passed":false,"stderr":"","stdout":"{\"observations\": [{\"check\": \"long alternate path\", \"actual\": [[10, 11], [10, 13], [11, 12], [12, 13]], \"expected\": [[10, 11], [11, 12], [12, 13]], \"passed\": false}, {\"check\": \"single necessary edge\", \"actual\": [[10, 11]], \"expected\": [[10, 11]], \"passed\": true}, {\"check\": \"short alternate path\", \"actual\": [[10, 11], [11, 12]], \"expected\": [[10, 11], [11, 12]], \"passed\": true}, {\"check\": \"empty\", \"actual\": [], \"expected\": [], \"passed\": true}, {\"check\": \"isolated nodes\", \"actual\": [], \"expected\": [], \"passed\": true}, {\"check\": \"duplicate declaration\", \"actual\": [[10, 11]], \"expected\": [[10, 11]], \"passed\": true}, {\"check\": \"fork has no redundancy\", \"actual\": [[10, 11], [10, 12]], \"expected\": [[10, 11], [10, 12]], \"passed\": true}, {\"check\": \"variable-length shortcut\", \"actual\": [[0, 1], [0, 3], [1, 2], [2, 3]], \"expected\": [[0, 1], [1, 2], [2, 3]], \"passed\": false}], \"passed\": false}\n"},"broken":{"elapsed_ms":39.79,"exit_code":1,"observations":[{"actual":[],"check":"long alternate path","expected":[[10,11],[11,12],[12,13]],"passed":false},{"actual":[],"check":"single necessary edge","expected":[[10,11]],"passed":false},{"actual":[],"check":"short alternate path","expected":[[10,11],[11,12]],"passed":false},{"actual":[],"check":"empty","expected":[],"passed":true},{"actual":[],"check":"isolated nodes","expected":[],"passed":true},{"actual":[],"check":"duplicate declaration","expected":[[10,11]],"passed":false},{"actual":[],"check":"fork has no redundancy","expected":[[10,11],[10,12]],"passed":false},{"actual":[],"check":"variable-length shortcut","expected":[[0,1],[1,2],[2,3]],"passed":false}],"passed":false,"stderr":"","stdout":"{\"observations\": [{\"check\": \"long alternate path\", \"actual\": [], \"expected\": [[10, 11], [11, 12], [12, 13]], \"passed\": false}, {\"check\": \"single necessary edge\", \"actual\": [], \"expected\": [[10, 11]], \"passed\": false}, {\"check\": \"short alternate path\", \"actual\": [], \"expected\": [[10, 11], [11, 12]], \"passed\": false}, {\"check\": \"empty\", \"actual\": [], \"expected\": [], \"passed\": true}, {\"check\": \"isolated nodes\", \"actual\": [], \"expected\": [], \"passed\": true}, {\"check\": \"duplicate declaration\", \"actual\": [], \"expected\": [[10, 11]], \"passed\": false}, {\"check\": \"fork has no redundancy\", \"actual\": [], \"expected\": [[10, 11], [10, 12]], \"passed\": false}, {\"check\": \"variable-length shortcut\", \"actual\": [], \"expected\": [[0, 1], [1, 2], [2, 3]], \"passed\": false}], \"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."}}