Source-linked AI summary
Time-Optimal APSP and Matrix Multiplication in Classes of Linear Neighborhood Complexity
Édouard Bonnet, Julien Duron, Marcin Pilipczuk, Marek Sokołowski, Szymon Toruńczyk
TL;DR
The paper asks how far efficient graph algorithms extend beyond sparse classes and beyond settings where low-width structural witnesses are supplied. It uses linear neighborhood complexity and related decompositions to obtain optimal algorithms for shortest paths and adjacency-matrix products, while extending the framework to bounded VC density and small-pattern detection. The main outcomes include O(n^2) All-Pairs Shortest Paths and preprocessing for O(n) matrix-vector products, alongside randomized near-linear detection algorithms for triangles, K4, and K5.
Problem
Efficient algorithms for structured dense graph classes often require a low twin-width or merge-width witness, whose polynomial-time construction remains open.
Method
The paper exploits linear neighborhood complexity through constant-width sd-degeneracy sequences and interval biclique partitions, extending the approach to classes of VC density ρ.
Results
The paper obtains O(n^2) All-Pairs Shortest Paths, O(n^2) preprocessing with O(n) adjacency matrix-vector products, and randomized near-linear small-pattern detection in linear-neighborhood-complexity classes.
Takeaways & Limitations
Linear neighborhood complexity supports time-optimal algorithms across shortest paths, matrix multiplication, and triangle detection, while also covering structured dense graph classes.
Takeaways & Limitations
For K5 detection, the stated result is randomized and includes polylogarithmic factors; moreover, k-Clique has an ETH-based lower bound in some linear-neighborhood-complexity class.
Abstract
from arXiv · showhide
The notion of linear neighborhood complexity is a very general structural assumption on a graph class, covering most classes of sparse graphs such as planar graphs, graphs excluding a fixed (topological) minor, or bounded expansion graphs, as well as many structured classes of dense graphs, such as graphs of bounded clique-width, twin-width, merge-width, or flip-width. In this work, we present $O(n^2)$-time optimal algorithms for $n$-vertex graphs coming from a class of linear neighborhood complexity for the following problems: $\bullet$ All-Pairs Shortest Paths, $\bullet$ the multiplication of the adjacency matrix $M$ of the input graph with any $n \times n$ matrix. More specifically, after a quadratic preprocessing, we can multiply $M$ with any $n$-vector in $O(n)$ time. This solves several questions raised in [Bonnet, Kim, Geniet, Moon; ICALP '26], and improves and generalizes results in several other recent papers [Bonnet, Giocanti, Ossona de Mendez, Thomassé; STACS '23], [Bannach, Marwitz, Tantau; STACS '24], [Anand, van den Brand, McCarty; NeurIPS '26], [Kozma, Opler '26], and [Cardinal, McCarty, Yuditsky '26]. We also extend our results to classes of bounded VC density. In classes of linear neighborhood complexity, we also give a triangle-detection algorithm in randomized linear time $O(n+m)$ in $n$-vertex $m$-edge graphs, a $K_4$-detection algorithm in randomized $O(n \log^5 n + m \log n)$ or deterministic $O(n^2)$ time, and a $K_5$-detection algorithm in randomized $O(n \log^9 n + m \log^5 n)$ time.
1 Introduction
The paper studies algorithmic tractability under linear neighborhood complexity, a framework spanning sparse and dense structured graph classes. It develops optimal or near-optimal algorithms for shortest paths, matrix multiplication, and small-pattern detection, with extensions to bounded VC density.
- Motivation: The paper addresses the open problem of efficiently producing low-width witnesses for structured graph classes.Prior algorithms often require a low twin-width or merge-width witness as part of the input.
- Structural setting: Linear neighborhood complexity bounds the number of distinct neighborhood traces on every nonempty vertex subset by a constant times its size.The framework also includes VC density ρ, where the trace count is bounded by c|A|^ρ.
- sd-degeneracy sequences: O(n^2) time suffices to output an sd-degeneracy sequence of constant width for graphs in any class of linear neighborhood complexity.A randomized expected-time version is also provided, while the broader VC-density result gives width O_C(n^(1−1/ρ)).
- Shortest paths: O(n^2) time solves All-Pairs Shortest Paths in every class of linear neighborhood complexity.The route uses an interval biclique partition with O(n) bicliques and a shortest-path-tree algorithm running in O(n+b), independent of the edge count.
- Matrix multiplication: O(n^2) preprocessing supports each adjacency matrix-vector product in O(n) time, and therefore multiplies the adjacency matrix by any n × n matrix in O(n^2) time.These results answer a question beyond bounded twin-width and remove extra polylogarithmic factors from earlier algorithms.
- Small patterns: Small-pattern detection runs in expected O(n+m) time for triangles, expected O(n log^5 n + m log n) or deterministic O(n^2) for K4, and expected O(n log^9 n + m log^5 n) for K5.The triangle result was previously unavailable even for more restricted bounded clique-width and witness-free bounded twin-width inputs.
2 Preliminaries
The preliminaries define neighborhood-based graph parameters, sd-degeneracy sequences, signed tree models, and interval biclique partitions, then connect these representations to fast adjacency-matrix–vector multiplication.
- Neighborhood complexity: Linear neighborhood complexity bounds the number of distinct neighborhood traces on any vertex subset by a constant times its size.The paper also defines VC density and polynomial neighborhood complexity through the growth rate of neighborhood traces.
- Symmetric difference and sd-degeneracy: Symmetric difference measures how many vertices distinguish two neighborhoods, with d-near-twins satisfying sdG(u, v) ≤ d.The symmetric difference of a graph is the smallest d guaranteeing such a pair in every induced subgraph with at least two vertices.
- Symmetric difference and sd-degeneracy: An sd-degeneracy sequence repeatedly pairs vertices while removing only each pair’s first vertex, and its width records the maximum allowed neighborhood difference.This gives an elimination-style characterization of sd-degeneracy bounded by d.
- Signed tree models and interval biclique partitions: Signed tree models represent adjacency using positive and negative transversal pairs in a full binary tree, with leaves as graph vertices.A leaf pair is adjacent exactly when it is covered by a positive transversal pair; negative pairs therefore encode non-adjacency.
- Signed tree models and interval biclique partitions: An sd-degeneracy sequence of width d can be transformed into an interval biclique partition with O(dn) bicliques in O(dn log n + m) time.Such a partition supports computing MX in O(n + b) time for an n-vector X when it contains b bicliques.
3 Finding an sd-degeneracy sequence deterministically
This section develops a quadratic-time data structure for testing near-twin pairs and uses it to construct bounded-width sd-degeneracy sequences, including a generalized exponent-α guarantee.
- Near-twin queries: An O(n^2)-time data structure answers whether sdG(u, v) ≤ d in O(d) time for any queried vertex pair.It concatenates all adjacency vectors into a length-n^2 binary word and answers comparisons using constant-time longest-common-extension queries.
- Near-twin queries: The query procedure scans matching runs in two adjacency vectors and decrements its difference budget whenever it finds a mismatch.Its correctness follows from maintaining the number of positions adjacent to exactly one of u and v.
- Near-twin queries: For constant d, all d-near-twin pairs can be listed in O(dn^2) time.The algorithm queries every ordered pair after building the quadratic-size data structure.
- Constructing sd-degeneracy sequences: A hereditary class with versatile symmetric difference of exponent α admits an O_C(n^(2+α))-time sd-degeneracy algorithm of width O_C(n^α).The construction repeatedly finds disjoint near-twin pairs in induced subgraphs and removes their first vertices in batches.
- Constructing sd-degeneracy sequences: For bounded versatile symmetric difference, the construction specializes to an O_C(n^2)-time algorithm producing an sd-degeneracy sequence of width O_C(1).This is obtained as the exponent-0 case of the generalized construction and implies the earlier constant-width result.
4 SSSP in graphs given with an interval biclique partition
The section develops a linear-time Interval-Intersect structure and uses it to compute single-source shortest-path trees from interval biclique partitions in O(n+b) time.
- SSSP from interval biclique partitions: O(n + b) time computes a shortest-path tree from a source in an n-vertex graph with an interval biclique partition of b bicliques.Two Interval-Intersect instances enumerate undiscovered vertices and unprocessed biclique sides during BFS.
- Interval intersections data structure: O(n + |A| + q) total time is achieved for Interval-Intersect on universe size N in the word RAM model.The structure supports online interval queries over active labeled intervals.
- SSSP from interval biclique partitions: At most n Dscatter queries and O(b) Dgather queries yield total SSSP processing time O(n+b), including the interval-intersection queries.The procedure remains an ordinary BFS, with bespoke neighbor listing through the two data structures.
- Interval intersections data structure: O(N log N + |A| + q) time supports quasi-linear interval intersections through a directed graph with one-time vertex visits.Queries decompose into at most two searches, and previously visited vertices are never revisited.
- Interval intersections data structure: Block decomposition and bootstrapping extend the tiny-universe structure to universe size Nmax while preserving O(N + |A| + q) processing time.Intervals are represented through intersecting blocks, fully contained core blocks, and within-block fringe intervals.
- Interval intersections data structure: O(ℓ + |A| + q) time handles tiny universes of size at most ℓ using a global table computable in O(2^ℓ^2) time.The table maps each interval query and state to intersecting and remaining intervals.
5 Wrap-up of the algorithmic corollaries
The paper combines constant-width sd-degeneracy sequences, interval biclique partitions, and shortest-path procedures to obtain quadratic APSP and matrix multiplication algorithms.
- All-Pairs Shortest Paths: O_C(n^2) time solves All-Pairs Shortest Paths for every graph class C of linear neighborhood complexity.The construction computes a constant-width sd-degeneracy sequence, derives an O(n)-biclique interval partition, and invokes the single-source procedure from every vertex.
- Matrix multiplication: O_C(n^2) preprocessing yields a data structure computing MX in O_C(n) time for any n-vector X and adjacency matrix M.The result uses an interval biclique partition with O(n) bicliques and the matrix-vector multiplication lemma.
- Matrix multiplication: O_C(n^2) time computes MN for any n × n matrix N.This follows by applying the matrix-vector data structure across the columns of N.
6 Finding an sd-degeneracy sequence in randomized linear time
The section uses VC-density tools and randomized sampling to find many near-twin pairs, then repeatedly removes them to construct sd-degeneracy sequences efficiently.
- Near-twin pairing: O_c,ρ,δ(|U|) disjoint pairs of O_c,ρ,δ(n^α)-near-twins are found in expected time for sufficiently large vertex subsets U.Here α = 1 − 1/ρ, and the algorithm handles both twin-free and general inputs.
- Near-twin pairing: Private pendant vertices reduce the general case to the twin-free case without increasing returned symmetric differences after deletion.The augmented graph has polynomial neighborhood complexity with adjusted constant c+2 and at most twice as many vertices.
- Sequence construction: A randomized algorithm outputs an sd-degeneracy sequence of width O_C(n^(1−1/ρ)) for graph classes of VC density ρ.The construction repeatedly selects half the current vertices with smallest degree, pairs near-twins, and deletes one endpoint from each pair.
- Sequence construction: The resulting sequence has width O_c,ρ(n^α), with α = 1 − 1/ρ.Each appended pair is a near-twin pair in the current induced subgraph, whose symmetric difference cannot increase after deletions.
- Sequence construction: O_c,ρ(n + m) expected time constructs the sequence in an n-vertex, m-edge graph.Maintained degrees and cumulative neighbor updates make the iterative process linear in the input size in expectation.
7 Finding Small Patterns
The section develops randomized almost-linear algorithms for detecting triangles, K4s, and K5s in graph classes of linear neighborhood complexity, alongside a deterministic quadratic K4 algorithm. These results use sd-degeneracy sequences and, for larger cliques, Welzl orders with interval-based geometric data structures.
- Triangle Detection: Expected O(n + m) time suffices to find a triangle in n-vertex m-edge graphs from a class of linear neighborhood complexity.The algorithm uses an sd-degeneracy sequence and static adjacency queries.
- Triangle Detection: The triangle algorithm processes vertices through induced subgraphs, preserving a triangle recursively when none containing the current vertex is found.At each step, unsuccessful searches replace a possible triangle through ui with one through vi.
- K4 Detection: Expected O(n log5 n + m log n) or deterministic O(n2) time suffices to detect a K4.The deterministic algorithm preprocesses the adjacency matrix and performs O(n)-time matrix-vector products per bounded-width iteration.
- K4 Detection: The randomized K4 algorithm combines an sd-degeneracy sequence with a Welzl order representing every neighborhood as O(log2 n) intervals.It tests interval pairs using rectangle queries over a planar point set encoding graph edges.
- K5 Detection: Expected O(n log9 n + m log5 n) time suffices to detect a K5 using four-dimensional orthogonal range queries.The queries detect a triangle among three interval ranges, which yields a five-vertex clique.
- Limits: The ETH-based lower bound shows that almost-linear dependence on n cannot hold uniformly for all clique sizes k on some such graph class.For a class of linear neighborhood complexity, k-Clique cannot be solved in time f(k)n^o(k / log k) unless ETH fails.
A Neighborhood complexity and versatile symmetric difference
The section connects VC density and linear neighborhood complexity to versatile symmetric difference through set-system packing arguments. This structural property supplies many disjoint vertex pairs with controlled neighborhood differences.
- VC Density and Packing: Haussler’s packing lemma provides close pairs of distinct sets in set systems with bounded VC dimension and polynomial shatter growth.The lemma bounds VC dimension and guarantees two members with small symmetric difference.
- Algorithmic Consequence: Bounded versatile symmetric difference is the structural bridge enabling constant-width sd-degeneracy sequences and the paper’s quadratic algorithms.The paper defines versatility through linearly many disjoint close pairs in every induced subgraph and uses it with longest-common-extension data structures.
- Versatile Symmetric Difference: For every fixed c and ρ, every n-vertex graph with (c, ρ)-polynomial neighborhood complexity contains at least ⌊n/8⌋ disjoint pairs with sdG(u, v) ≤ dn1−1/ρ.The constant d depends only on c and ρ.
- Versatile Symmetric Difference: Every hereditary graph class of VC density ρ has versatile symmetric difference exponent 1 − 1/ρ, and every class of linear neighborhood complexity has bounded versatile symmetric difference.The conclusion follows by applying the pair bound to every graph in the class.
- Proof Structure: The proof handles graphs with many twins by pairing vertices within twin classes, yielding at least ⌊n/8⌋ pairs satisfying the required bound.This is the case when the largest twin-free subset has size at most n/2.
- Proof Structure: When more than half the vertices have distinct neighborhoods, repeated packing-lemma applications produce disjoint pairs with symmetric difference at most k · 41/ρ n1−1/ρ.The construction removes each selected pair and repeats while the remaining set system is sufficiently large.