That does sound at least conceptually simpler.
You mean PBFS from https://arxiv.org/pdf/2410.15920, right? Its complexity bound seems somewhat worse than GGT.
Summarizing the different algorithms I see (FP = solve each min-cut from scratch), where:
- n: number of transactions
- m: number of dependencies (which is itself \mathcal{O}(n) for sparse graphs and \mathcal{O}(n^2) for dense graphs).
- k: number of chunks (up to \mathcal{O}(n)).
| Algorithm | Complexity | Sparse | Dense |
|---|---|---|---|
| FP (generic) | \mathcal{O}(k n^2 m) | \mathcal{O}(n^4) | \mathcal{O}(n^5) |
| FP (FIFO) | \mathcal{O}(k n^3) | \mathcal{O}(n^4) | \mathcal{O}(n^4) |
| FP (max label) | \mathcal{O}(k n^2 \sqrt{m}) | \mathcal{O}(n^{3.5}) | \mathcal{O}(n^4) |
| FP (dynamic trees) | \mathcal{O}(knm \log(n^2/m)) | \mathcal{O}(n^3 \log n) | \mathcal{O}(n^4) |
| PBFS | \mathcal{O}(n^2 m) | \mathcal{O}(n^3) | \mathcal{O}(n^4) |
| GGT (generic) | \mathcal{O}(n^2 m) | \mathcal{O}(n^3) | \mathcal{O}(n^4) |
| GGT (FIFO) | \mathcal{O}(n^3) | \mathcal{O}(n^3) | \mathcal{O}(n^3) |
| GGT (max label) | \mathcal{O}(n^2 \sqrt{m}) | \mathcal{O}(n^{2.5}) | \mathcal{O}(n^3) |
| GGT (dynamic trees) | \mathcal{O}(nm \log(n^2/m)) | \mathcal{O}(n^2 \log n) | \mathcal{O}(n^3) |
We’ll need to experiment with specialized implementations though, because seeing papers talk about problems with millions of nodes means that what they consider “practical problems” may be very different than what we have in mind (we’ll probably prefer simpler algorithms over better complexity ones) but also that many data-structure optimizations may not apply in their settings. However, we also care more about worst-case performance than they do, presumably.