Graph algorithms reach matrix multiplication’s time bound
The proof improved running-time guarantees for all the graph problems studied in earlier work by Kratsch and Spinrad, essentially matching conditional limits.
Edited by Boris Djordjevic · Paperfoot
The paper proved that all the structural graph problems considered in Kratsch and Spinrad’s 2003 and 2006 work admitted algorithms with a matrix-multiplication running-time bound. Graphs represent objects and their connections; matrix multiplication combines tables of numbers. Earlier algorithms had slower running-time guarantees.
The proof showed that those slower bounds were not necessary for these problems. The new guarantee essentially matched earlier conditional limits on possible speed, based on three unproved assumptions about variants of finding triangles in graphs. The authors also made partial progress by improving algorithms for other structural graph problems.
Why it matters
The proof settled a question open for more than 20 years: whether these graph problems required more time than the earlier conditional limits suggested.
Caveats
The limits on further speedups depended on unproved hardness assumptions, so they were not unconditional barriers. The paper is an arXiv preprint.
In this paper
structural graph theory fine-grained complexity
What it shows
- All problems studied by Kratsch and Spinrad admit an O(n^ω) time algorithm.
In this paper, we resolve this question and show that the latter is the case: all problems admit an O(n^ω) time algorithm.
Abstract
- In an AT-free graph, the total number of distinct connected components across all neighborhood-deleted subgraphs is at most 400 n log n.
Then there are at most \mathcal{O}(n\log n) distinct components across all \mathbf{G}_{x}; that is, |\mathcal{C}|≤ 400 n\log n for \mathcal{C}\coloneqq\bigcup_{x\in V}\mathcal{C}_{x}.
2.2 Recognizing AT-free Graphs in Matrix Multiplication Time
Quoted word for word from the full text on arXiv.
The paper
Asteroidal Triples and Friends in (Likely Necessary) Matrix Multiplication Time
arXiv, Oct 15, 2026, Open access, CC BY, Preprint, not peer-reviewed