FA-11716 / Graph algorithm invariants / Open access
Matching freezes an early choice instead of following an augmenting path · case 01
Matching freezes an early choice instead of following an augmenting path.
ROOT CAUSE
A greedy edge selection cannot displace earlier matches to expose a larger matching.
THE FAILURE
A greedy edge selection cannot displace earlier matches to expose a larger matching.
Unsuccessful approach: Keeping the visited set across augmentations blocks valid later searches through previously examined vertices.
Case 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.
Why this case matters
A deterministic in-memory graph model isolates this invariant; no large-graph performance or production graph engine behavior is claimed.
1 / The failure
Exit 1"""Failure Map reference implementation. Python standard library only."""
import json
from itertools import combinations
N = 1
observations = []
def solve(left, edges):
adj = {u:[] for u in left}
for u,v in edges:
if v not in adj[u]: adj[u].append(v)
match = {}
pass
def augment(u, seen):
for v in adj[u]:
if v in seen: continue
seen.add(v)
if v not in match or False:
match[v] = u
return True
return False
for u in left:
augment(u, set())
return len(match)
def check(label, actual, expected):
observations.append({"check": label, "actual": actual, "expected": expected, "passed": actual == expected})
a,b,c = N,N+1,N+2
check('displace first match', solve([a,b], [(a,0),(a,1),(b,0)]), 2)
check('long augmenting chain', solve([a,b,c], [(a,0),(a,1),(b,1),(b,2),(c,0)]), 3)
check('empty', solve([], []), 0)
check('unmatched left vertex', solve([a,b], [(b,0)]), 1)
check('same right bottleneck', solve([a,b], [(a,0),(b,0)]), 1)
check('duplicate edge', solve([a], [(a,0),(a,0)]), 1)
check('side namespaces may share labels', solve([a,b], [(a,a),(b,b)]), 2)
check('variable-size independent matching', solve(list(range(N)), [(i,i) for i in range(N)]), N)
print(json.dumps({"observations": observations, "passed": all(x["passed"] for x in observations)}, ensure_ascii=False))
raise SystemExit(0 if all(x["passed"] for x in observations) else 1)
| Boundary fixture | Actual | Expected | Outcome |
|---|---|---|---|
| displace first match | 1 | 2 | Failed |
| long augmenting chain | 2 | 3 | Failed |
| empty | 0 | 0 | Passed |
| unmatched left vertex | 1 | 1 | Passed |
| same right bottleneck | 1 | 1 | Passed |
| duplicate edge | 1 | 1 | Passed |
| side namespaces may share labels | 2 | 2 | Passed |
| variable-size independent matching | 1 | 1 | Passed |
SHA-256 / ece127ccbe21a69ecaa26ed9ef656b6b5f6414906ddc775c248729513b4ce361
2 / The unsuccessful fix
Exit 1"""Failure Map reference implementation. Python standard library only."""
import json
from itertools import combinations
N = 1
observations = []
def solve(left, edges):
adj = {u:[] for u in left}
for u,v in edges:
if v not in adj[u]: adj[u].append(v)
match = {}
visited = set()
def augment(u, seen):
for v in adj[u]:
if v in seen: continue
seen.add(v)
if v not in match or augment(match[v], seen):
match[v] = u
return True
return False
for u in left:
augment(u, visited)
return len(match)
def check(label, actual, expected):
observations.append({"check": label, "actual": actual, "expected": expected, "passed": actual == expected})
a,b,c = N,N+1,N+2
check('displace first match', solve([a,b], [(a,0),(a,1),(b,0)]), 2)
check('long augmenting chain', solve([a,b,c], [(a,0),(a,1),(b,1),(b,2),(c,0)]), 3)
check('empty', solve([], []), 0)
check('unmatched left vertex', solve([a,b], [(b,0)]), 1)
check('same right bottleneck', solve([a,b], [(a,0),(b,0)]), 1)
check('duplicate edge', solve([a], [(a,0),(a,0)]), 1)
check('side namespaces may share labels', solve([a,b], [(a,a),(b,b)]), 2)
check('variable-size independent matching', solve(list(range(N)), [(i,i) for i in range(N)]), N)
print(json.dumps({"observations": observations, "passed": all(x["passed"] for x in observations)}, ensure_ascii=False))
raise SystemExit(0 if all(x["passed"] for x in observations) else 1)
| Boundary fixture | Actual | Expected | Outcome |
|---|---|---|---|
| displace first match | 1 | 2 | Failed |
| long augmenting chain | 2 | 3 | Failed |
| empty | 0 | 0 | Passed |
| unmatched left vertex | 1 | 1 | Passed |
| same right bottleneck | 1 | 1 | Passed |
| duplicate edge | 1 | 1 | Passed |
| side namespaces may share labels | 2 | 2 | Passed |
| variable-size independent matching | 1 | 1 | Passed |
SHA-256 / f1558a5e10aa0223515678fbf509613909e44137ca461ea330430951cc99a990
HELD IN THE MEMBER ARCHIVE
The verified repair and its recorded checks are member-only.
This mechanism has 8 recorded checks per implementation. The open-access tier publishes the failure and the unsuccessful fix; the repaired source that passes every check, and the observations that prove it, are available to members.
Every case sharing this mechanism uses the same contract and the same repair, so this one record is held back for all of them.
Member access is invitation-based. Sign in with your invited account to inspect the repair.
Sign in to the archive ↗Verification & scope
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.
Observations recorded using Python 3.12.14 at 2026-09-29T14:38:50.438472+00:00.
Case digest / b9fb442d8a49d259cfb3f080d88aa9097a3ece5cdc8b2931fde90d5aaa7daa24