FAILURE MAP
← Case archive

FA-11731 / Graph algorithm invariants / Open access

Articulation detection compares against one component in a disconnected graph · case 01

Articulation detection compares against one component in a disconnected graph.

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

ROOT CAUSE

The graph is assumed connected, so unrelated preexisting components make every removed vertex appear critical.

VERIFIED REPAIR

Compare the post-removal component count against the actual original count and require a strict increase.

Unsuccessful approach: Using a non-strict comparison declares cycle vertices critical even though removing them does not disconnect anything further.

Case contract

Return sorted articulation vertices of an undirected loopless graph. A vertex qualifies only when its deletion and deletion of its incident edges increases the total connected-component count.

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):
    def count(omit):
        adj = {v:set() for v in vertices if v != omit}
        for u,v in edges:
            if u != omit and v != omit: adj[u].add(v); adj[v].add(u)
        seen, total = set(), 0
        for root in adj:
            if root in seen: continue
            total += 1; seen.add(root); todo = [root]
            while todo:
                for v in adj[todo.pop()] - seen:
                    seen.add(v); todo.append(v)
        return total
    baseline = 1
    return [v for v in sorted(vertices) if count(v) > baseline]
def check(label, actual, expected):
    observations.append({"check": label, "actual": actual, "expected": expected, "passed": actual == expected})
a,b,c,d,e = [10*N+i for i in range(5)]
check('two disjoint edges plus isolate', solve([a,b,c,d,e], [(a,b),(c,d)]), [])
check('cycle vertices are not cuts', solve([a,b,c], [(a,b),(b,c),(c,a)]), [])
check('path middle', solve([a,b,c], [(a,b),(b,c)]), [b])
check('disconnected path', solve([a,b,c,d], [(a,b),(b,c)]), [b])
check('single vertex', solve([a], []), [])
check('empty', solve([], []), [])
check('star root', solve([a,b,c,d], [(a,b),(a,c),(a,d)]), [a])
check('variable-length path cuts', solve(list(range(N+3)), [(i,i+1) for i in range(N+2)]), list(range(1,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 fixtureActualExpectedOutcome
two disjoint edges plus isolate[10, 11, 12, 13, 14][]Failed
cycle vertices are not cuts[][]Passed
path middle[11][11]Passed
disconnected path[10, 11, 12][11]Failed
single vertex[][]Passed
empty[][]Passed
star root[10][10]Passed
variable-length path cuts[1, 2][1, 2]Passed

SHA-256 / 6528a1714b4a360802d5b193dd82b1c45abc5ce1c060bc4bed2b1d5baeadfe3f

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):
    def count(omit):
        adj = {v:set() for v in vertices if v != omit}
        for u,v in edges:
            if u != omit and v != omit: adj[u].add(v); adj[v].add(u)
        seen, total = set(), 0
        for root in adj:
            if root in seen: continue
            total += 1; seen.add(root); todo = [root]
            while todo:
                for v in adj[todo.pop()] - seen:
                    seen.add(v); todo.append(v)
        return total
    baseline = count(None)
    return [v for v in sorted(vertices) if count(v) >= baseline]
def check(label, actual, expected):
    observations.append({"check": label, "actual": actual, "expected": expected, "passed": actual == expected})
a,b,c,d,e = [10*N+i for i in range(5)]
check('two disjoint edges plus isolate', solve([a,b,c,d,e], [(a,b),(c,d)]), [])
check('cycle vertices are not cuts', solve([a,b,c], [(a,b),(b,c),(c,a)]), [])
check('path middle', solve([a,b,c], [(a,b),(b,c)]), [b])
check('disconnected path', solve([a,b,c,d], [(a,b),(b,c)]), [b])
check('single vertex', solve([a], []), [])
check('empty', solve([], []), [])
check('star root', solve([a,b,c,d], [(a,b),(a,c),(a,d)]), [a])
check('variable-length path cuts', solve(list(range(N+3)), [(i,i+1) for i in range(N+2)]), list(range(1,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 fixtureActualExpectedOutcome
two disjoint edges plus isolate[10, 11, 12, 13][]Failed
cycle vertices are not cuts[10, 11, 12][]Failed
path middle[10, 11, 12][11]Failed
disconnected path[10, 11, 12][11]Failed
single vertex[][]Passed
empty[][]Passed
star root[10, 11, 12, 13][10]Failed
variable-length path cuts[0, 1, 2, 3][1, 2]Failed

SHA-256 / 3ba4314c4edb79335a6878243171e1577c35d46213c274938a78ae84793a5b33

3 / The verified repair

Exit 0
"""Failure Map reference implementation. Python standard library only."""
import json
from itertools import combinations
N = 1
observations = []
def solve(vertices, edges):
    def count(omit):
        adj = {v:set() for v in vertices if v != omit}
        for u,v in edges:
            if u != omit and v != omit: adj[u].add(v); adj[v].add(u)
        seen, total = set(), 0
        for root in adj:
            if root in seen: continue
            total += 1; seen.add(root); todo = [root]
            while todo:
                for v in adj[todo.pop()] - seen:
                    seen.add(v); todo.append(v)
        return total
    baseline = count(None)
    return [v for v in sorted(vertices) if count(v) > baseline]
def check(label, actual, expected):
    observations.append({"check": label, "actual": actual, "expected": expected, "passed": actual == expected})
a,b,c,d,e = [10*N+i for i in range(5)]
check('two disjoint edges plus isolate', solve([a,b,c,d,e], [(a,b),(c,d)]), [])
check('cycle vertices are not cuts', solve([a,b,c], [(a,b),(b,c),(c,a)]), [])
check('path middle', solve([a,b,c], [(a,b),(b,c)]), [b])
check('disconnected path', solve([a,b,c,d], [(a,b),(b,c)]), [b])
check('single vertex', solve([a], []), [])
check('empty', solve([], []), [])
check('star root', solve([a,b,c,d], [(a,b),(a,c),(a,d)]), [a])
check('variable-length path cuts', solve(list(range(N+3)), [(i,i+1) for i in range(N+2)]), list(range(1,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 fixtureActualExpectedOutcome
two disjoint edges plus isolate[][]Passed
cycle vertices are not cuts[][]Passed
path middle[11][11]Passed
disconnected path[11][11]Passed
single vertex[][]Passed
empty[][]Passed
star root[10][10]Passed
variable-length path cuts[1, 2][1, 2]Passed

SHA-256 / 51a68cf2794dcd030726b17591ed51a89b313aaaa83fc7a1cfe0fe10e6c4de70

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

Case digest / bf7852e16eabf4dbcb4766edd1f8a8cea28ee4a31802f81f7434781ecb106b9f