FA-11724 / Graph algorithm invariants / Member archive

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

Transitive reduction lets the candidate edge justify its own removal.

Member previewVariant 4 · 3 implementations · 8 checks per implementation

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.

One recorded failure

Sample boundary fixture

This sample comes from the broken implementation of a controlled reproducer.

Boundary fixture	Actual	Expected	Outcome
long alternate path	`[]`	`[[40, 41], [41, 42], [42, 43]]`	Failed

MEMBER ARCHIVE

The complete case is available to members.

This record includes three runnable implementations, regression fixtures, execution results, and source hashes.

Member access is invitation-based. Sign in with your invited account to inspect the sources.