# Can the Duan et al. 2025 "breaking the sorting barrier" faster-than-Dijkstra SSSP algorithm speed up Yamada–Kinoshita negative-cycle enumeration?
## Summary
This postmortem explores whether Duan et al.'s advanced single-source shortest path (SSSP) algorithm for nonnegative weights can accelerate Yamada–Kinoshita's method for enumerating negative cycles. Key conclusions:
- Duan et al.'s algorithm cannot be directly integrated into Yamada–Kinoshita due to **nonnegative weight constraints**.
- Repetitive SSSP calls in Yamada–Kinoshita internally handle negative edges, precluding safe use of Duan’s method.
- The exponential output complexity of negative cycle enumeration further limits practical gains.
## Root Cause
The critical incompatibility arises from irreconcilable algorithmic requirements:
* **Duan et al.'s SSSP demands nonnegative edge weights**, but Yamada–Kinoshita operates on graphs containing negative cycles.
* Johnson-style reweighting (using potentials) can't precondition graphs with negative cycles, as it requires solving an initial feasibility problem (which presupposes cycle enumeration).
* Core components of Yamada–Kinoshita inherently process negative edges via Bellman-Ford-like steps, making Dijkstra replacement impossible.
## Why This Happens in Real Systems
In practical settings, engineers frequently encounter scenarios where:
- Optimizing subroutine performance (like SSSP) seems promising but clashes with fundamental constraints.
- Theoretical breakthroughs (like Duan et al.) may appear broadly applicable, but edge-case constraints render them unusable in specific contexts.
- Reweighting techniques introduce hidden dependencies (e.g., requiring no negative cycles) that invalidate cross-algorithm compatibility.
## Real-World Impact
Failure to integrate these algorithms affects efficiency and correctness:
* Yamada–Kinoshita retains its worst-case exponential runtime for exhaustive cycle enumeration.
* Performance improvements remain capped at **O(|V|⋅|E|)** per SSSP call instead of Duan et al.’s **O(|V|)** on large graphs.
* Cyclic dependencies prevent parallelism—rewriting for compatibility would require redesigning Yamada–Kinoshita's core partitioning logic.
## Example or Code
Pseudocode snippet highlighting Yamada–Kinoshita's SSSP reliance:
```python
for vertex v in graph:
# Initialize distances with ∞ except v (distance=0)
dist = {...}
# Internal SSSP call WITH NEGATIVE
