# Time-Optimal APSP and Matrix Multiplication in Classes of Linear Neighborhood Complexity

Preprint · Édouard Bonnet, Julien Duron, Marcin Pilipczuk, Marek Sokołowski, Szymon Toruńczyk

- Archive id: arxiv:2608.25212
- Published: 2026-08-25
- arXiv: https://arxiv.org/abs/2608.25212
- Source URL: https://arxiv.org/abs/2608.25212
- PDF: https://arxiv.org/pdf/2608.25212
- Provenance: arxiv

## Abstract

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.

_Abstract reproduced under CC0-1.0 (arXiv descriptive metadata)._

---
Space Kitty Archive · https://space-kitty.com · API: https://space-kitty.com/api/v1 · MCP: https://space-kitty.com/mcp · Premium: $0.20/request via x402 (Base Sepolia (testnet)). Metadata: arXiv (CC0), OpenAlex (CC0), Europe PMC (CC BY/CC0 works), ClinicalTrials.gov.