FA-11726 / Graph algorithm invariants / Open access
Core decomposition stops after deleting only the initial low-degree frontier · case 01
Core decomposition stops after deleting only the initial low-degree frontier.
ROOT CAUSE
Degrees are not recomputed after vertices disappear, preventing cascading removals.
VERIFIED REPAIR
Repeatedly remove all vertices whose degree within the surviving induced graph is below k until stable.
Unsuccessful approach: Subtracting only one from each original degree guesses the cascade rather than measuring surviving neighbors.
Case contract
Return sorted vertices of the k-core of a simple undirected loopless graph, for nonnegative integer k. Repeated edges are ignored; all vertices survive k=0.
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, k):
adj = {v:set() for v in vertices}
for u,v in edges:
adj[u].add(v); adj[v].add(u)
active = set(vertices)
while True:
removed = {v for v in active if len(adj[v] & active) < k}
if not removed: break
active -= removed
break
return sorted(active)
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('path cascade', solve([a,b,c,d,e], [(a,b),(b,c),(c,d),(d,e)], 2), [])
check('star center loses multiple neighbors', solve([a,b,c,d], [(a,b),(a,c),(a,d)], 2), [])
check('triangle survives', solve([a,b,c,d], [(a,b),(b,c),(c,a),(c,d)], 2), [a,b,c])
check('zero threshold', solve([a,b], [], 0), [a,b])
check('isolates fail positive threshold', solve([a,b], [], 1), [])
check('empty', solve([], [], N), [])
check('duplicate edges not degree inflation', solve([a,b], [(a,b),(a,b)], 2), [])
check('variable-size cycle core', solve(list(range(N+2)), [(i,(i+1)%(N+2)) for i in range(N+2)], 2), list(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 |
|---|---|---|---|
| path cascade | [11, 12, 13] | [] | Failed |
| star center loses multiple neighbors | [10] | [] | Failed |
| triangle survives | [10, 11, 12] | [10, 11, 12] | Passed |
| zero threshold | [10, 11] | [10, 11] | Passed |
| isolates fail positive threshold | [] | [] | Passed |
| empty | [] | [] | Passed |
| duplicate edges not degree inflation | [] | [] | Passed |
| variable-size cycle core | [0, 1, 2] | [0, 1, 2] | Passed |
SHA-256 / 206abf336d5130d07916a1bd07b3545982b35047b9fd7577ce58aaa3632b2f38
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, k):
adj = {v:set() for v in vertices}
for u,v in edges:
adj[u].add(v); adj[v].add(u)
active = set(vertices)
while True:
removed = {v for v in active if len(adj[v]) - (bool(adj[v] - active)) < k}
if not removed: break
active -= removed
pass
return sorted(active)
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('path cascade', solve([a,b,c,d,e], [(a,b),(b,c),(c,d),(d,e)], 2), [])
check('star center loses multiple neighbors', solve([a,b,c,d], [(a,b),(a,c),(a,d)], 2), [])
check('triangle survives', solve([a,b,c,d], [(a,b),(b,c),(c,a),(c,d)], 2), [a,b,c])
check('zero threshold', solve([a,b], [], 0), [a,b])
check('isolates fail positive threshold', solve([a,b], [], 1), [])
check('empty', solve([], [], N), [])
check('duplicate edges not degree inflation', solve([a,b], [(a,b),(a,b)], 2), [])
check('variable-size cycle core', solve(list(range(N+2)), [(i,(i+1)%(N+2)) for i in range(N+2)], 2), list(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 |
|---|---|---|---|
| path cascade | [] | [] | Passed |
| star center loses multiple neighbors | [10] | [] | Failed |
| triangle survives | [10, 11, 12] | [10, 11, 12] | Passed |
| zero threshold | [10, 11] | [10, 11] | Passed |
| isolates fail positive threshold | [] | [] | Passed |
| empty | [] | [] | Passed |
| duplicate edges not degree inflation | [] | [] | Passed |
| variable-size cycle core | [0, 1, 2] | [0, 1, 2] | Passed |
SHA-256 / 22c7f09f8b312f3d5e8ad35309c25f58c5acebeac1c0b4f40a797393f420cbc2
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, k):
adj = {v:set() for v in vertices}
for u,v in edges:
adj[u].add(v); adj[v].add(u)
active = set(vertices)
while True:
removed = {v for v in active if len(adj[v] & active) < k}
if not removed: break
active -= removed
pass
return sorted(active)
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('path cascade', solve([a,b,c,d,e], [(a,b),(b,c),(c,d),(d,e)], 2), [])
check('star center loses multiple neighbors', solve([a,b,c,d], [(a,b),(a,c),(a,d)], 2), [])
check('triangle survives', solve([a,b,c,d], [(a,b),(b,c),(c,a),(c,d)], 2), [a,b,c])
check('zero threshold', solve([a,b], [], 0), [a,b])
check('isolates fail positive threshold', solve([a,b], [], 1), [])
check('empty', solve([], [], N), [])
check('duplicate edges not degree inflation', solve([a,b], [(a,b),(a,b)], 2), [])
check('variable-size cycle core', solve(list(range(N+2)), [(i,(i+1)%(N+2)) for i in range(N+2)], 2), list(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 |
|---|---|---|---|
| path cascade | [] | [] | Passed |
| star center loses multiple neighbors | [] | [] | Passed |
| triangle survives | [10, 11, 12] | [10, 11, 12] | Passed |
| zero threshold | [10, 11] | [10, 11] | Passed |
| isolates fail positive threshold | [] | [] | Passed |
| empty | [] | [] | Passed |
| duplicate edges not degree inflation | [] | [] | Passed |
| variable-size cycle core | [0, 1, 2] | [0, 1, 2] | Passed |
SHA-256 / fa13e6ad5ea30aacb76c1a6c67c12217da84e223115e8dbb6e6270758ee905d6
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.480684+00:00.
Case digest / 2bbeea69c6806f867d7ca2bbf0f3b3c818b21df4fee8609eb9c4189b0cf899c9