A theoretical preprint reports a quadratic-time method for finding shortest paths between every pair of vertices in graph classes with linear neighborhood complexity. For an n-vertex graph in any such class, the all-pairs shortest-path problem, or APSP, is solved in O_C(n^2) time. The subscript C indicates that the hidden constant depends on the graph class. The work is identified as arXiv:2608.25212v1 and dated 25 Aug 2026.
The route to that result begins with an sd-degeneracy sequence. For the target classes, the paper guarantees a sequence of constant width and gives a construction in O_C(n^2) time. A randomized procedure offers another route, returning a constant-width sequence in expected time O_C(|V(G)| + |E(G)|). Because that guarantee is expected, its stated running time is an average over the procedure's random choices, not a promise about every individual run.
The structural route to every-pair paths
Once the sequence is available, the main pipeline converts it into an interval biclique partition with O(n) bicliques in O(n log n + |E(G)|) time, also O(n^2) in the stated setting. A biclique is a complete connection between two groups of vertices, so this partition acts as a structured representation of the graph. Given such a partition with b bicliques and one source vertex, the shortest-path routine produces a shortest-path tree in O(n + b) time.
Running that one-source routine from every vertex gives the all-pairs result. The guarantee is for every graph class with linear neighborhood complexity, which makes the class condition central rather than incidental. It does not extend by itself to arbitrary graphs, and the constant hidden in O_C notation is not specified.
The same machinery reaches matrices and cliques
The same graph structure also supports matrix operations. For the adjacency matrix M of an n-vertex graph in the class, preprocessing takes O_C(n^2) time. After preprocessing, each product of M with a vector takes O_C(n) time, while multiplying M by an n-by-n matrix takes O_C(n^2) time. The guarantee concerns adjacency matrices from the specified graph classes, not arbitrary dense matrices.
Small-pattern searches receive similarly strong bounds. On n-vertex, m-edge graphs in the target classes, triangle detection has expected runtime O_C(n + m). For K4, the four-vertex clique, the paper gives an expected O_C(n log^5 n + m log n) algorithm and a deterministic O_C(n^2) alternative. K5 detection, for the five-vertex clique, has an expected O_C(n log^9 n + m log^5 n) runtime.
The word expected matters here. The triangle result, the near-linear K4 result and the K5 result are expected-time statements, not deterministic worst-case guarantees for every run. The K5 theorem is specific to that pattern and does not establish one uniform bound for cliques of every size.
The extension has a boundary
The authors extend the sequence construction beyond linear neighborhood complexity to graph classes described by VC density rho, with rho at least 1. The deterministic extension has parameter-dependent time and width bounds. A randomized version also supplies an expected-time sequence construction with parameter-dependent width and expected time O_C(|V(G)| + |E(G)|).
Using that extension, the paper states that APSP and multiplying an adjacency matrix by any n-by-n matrix take O(n^(3 - 1/rho)) time on graphs of VC density rho. This is a parameterized guarantee: the running time is expressed in terms of the class's VC-density value.
That broader reach comes with a boundary. Under ETH, the paper identifies a linear-neighborhood-complexity class in which k-Clique cannot be solved in the theorem's stated uniformly fast running-time form for any function f, unless ETH fails. The conclusion is conditional on ETH, so it is not an unconditional lower bound.
Taken together, the results form one linked package: a graph-class assumption yields a structural sequence, the sequence yields a biclique representation, and that representation supports shortest paths, matrix products and small-clique tests. The guarantees are most relevant when inputs are known to belong to the stated classes and, for some routines, when the required representation is supplied. Several of the pattern bounds are expected-time, while the k-Clique barrier depends on ETH.
Paper data and sources
Original title: Time-Optimal APSP and Matrix Multiplication in Classes of Linear Neighborhood Complexity
Authors: Édouard Bonnet, Julien Duron, Marcin Pilipczuk et al.
Journal/Repository: arXiv
Status: Preprint, not yet peer-reviewed
First online: 2026-08-25
DOI: Not available
Original paper · Full text