FA-11721 / Graph algorithm invariants / Open access

Transitive reduction lets the candidate edge justify its own removal · case 01

Transitive reduction lets the candidate edge justify its own removal.

Verified by executionVariant 1 · 8 checks per implementationDownload source bundle ↓JSON ↗

ROOT CAUSE

A reachability query includes the very edge being tested for redundancy.

THE FAILURE

A reachability query includes the very edge being tested for redundancy.

Unsuccessful approach: Checking only paths of at most two hops retains edges implied by longer paths.

Case 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.

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(vertices, edges):
    unique = sorted(set(edges))
    answer = []
    for edge in unique:
        u,v = edge
        adj = {x:set() for x in vertices}
        for a,b in unique:
            if False: continue
            adj[a].add(b)
        seen, todo = {u}, [u]
        while todo:
            x = todo.pop()
            for y in adj[x] - seen:
                seen.add(y)
                todo.append(y)
        if v not in seen: answer.append([u,v])
    return answer
def check(label, actual, expected):
    observations.append({"check": label, "actual": actual, "expected": expected, "passed": actual == expected})
a,b,c,d = [10*N+i for i in range(4)]
check('long alternate path', solve([a,b,c,d], [(a,b),(b,c),(c,d),(a,d)]), [[a,b],[b,c],[c,d]])
check('single necessary edge', solve([a,b], [(a,b)]), [[a,b]])
check('short alternate path', solve([a,b,c], [(a,b),(b,c),(a,c)]), [[a,b],[b,c]])
check('empty', solve([], []), [])
check('isolated nodes', solve([a,b], []), [])
check('duplicate declaration', solve([a,b], [(a,b),(a,b)]), [[a,b]])
check('fork has no redundancy', solve([a,b,c], [(a,b),(a,c)]), [[a,b],[a,c]])
check('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)])
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
long alternate path	`[]`	`[[10, 11], [11, 12], [12, 13]]`	Failed
single necessary edge	`[]`	`[[10, 11]]`	Failed
short alternate path	`[]`	`[[10, 11], [11, 12]]`	Failed
empty	`[]`	`[]`	Passed
isolated nodes	`[]`	`[]`	Passed
duplicate declaration	`[]`	`[[10, 11]]`	Failed
fork has no redundancy	`[]`	`[[10, 11], [10, 12]]`	Failed
variable-length shortcut	`[]`	`[[0, 1], [1, 2], [2, 3]]`	Failed

SHA-256 / 673135f98a402048447ed3f259324c4c7c91895c02920a2196c192b5f3a6c63a

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(vertices, edges):
    unique = sorted(set(edges))
    answer = []
    for edge in unique:
        u,v = edge
        adj = {x:set() for x in vertices}
        for a,b in unique:
            if (a,b) == edge: continue
            adj[a].add(b)
        seen, todo = {u}, [u]
        while todo:
            x = todo.pop()
            for y in adj[x] - seen:
                seen.add(y)
                if x == u: todo.append(y)
        if v not in seen: answer.append([u,v])
    return answer
def check(label, actual, expected):
    observations.append({"check": label, "actual": actual, "expected": expected, "passed": actual == expected})
a,b,c,d = [10*N+i for i in range(4)]
check('long alternate path', solve([a,b,c,d], [(a,b),(b,c),(c,d),(a,d)]), [[a,b],[b,c],[c,d]])
check('single necessary edge', solve([a,b], [(a,b)]), [[a,b]])
check('short alternate path', solve([a,b,c], [(a,b),(b,c),(a,c)]), [[a,b],[b,c]])
check('empty', solve([], []), [])
check('isolated nodes', solve([a,b], []), [])
check('duplicate declaration', solve([a,b], [(a,b),(a,b)]), [[a,b]])
check('fork has no redundancy', solve([a,b,c], [(a,b),(a,c)]), [[a,b],[a,c]])
check('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)])
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
long alternate path	`[[10, 11], [10, 13], [11, 12], [12, 13]]`	`[[10, 11], [11, 12], [12, 13]]`	Failed
single necessary edge	`[[10, 11]]`	`[[10, 11]]`	Passed
short alternate path	`[[10, 11], [11, 12]]`	`[[10, 11], [11, 12]]`	Passed
empty	`[]`	`[]`	Passed
isolated nodes	`[]`	`[]`	Passed
duplicate declaration	`[[10, 11]]`	`[[10, 11]]`	Passed
fork has no redundancy	`[[10, 11], [10, 12]]`	`[[10, 11], [10, 12]]`	Passed
variable-length shortcut	`[[0, 1], [0, 3], [1, 2], [2, 3]]`	`[[0, 1], [1, 2], [2, 3]]`	Failed

SHA-256 / 73d8d407ba544f6a9ffac34a1957ef65052d11fc1c5b8c9272f5de78230e92e2

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.

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.440522+00:00.

Case digest / df7a32a3882f036b7a4a4646cc26764a9720c6dac9e00d92412d93fcaf5b4e91