# Fast Shortest Path in Graphs With Sparse Signed Tree Models and Applications

Preprint · Édouard Bonnet, Colin Geniet, Eun Jung Kim, Sungmin Moon

- Archive id: arxiv:2602.16605
- Published: 2026-02-18
- arXiv: https://arxiv.org/abs/2602.16605
- Source URL: https://arxiv.org/abs/2602.16605
- PDF: https://arxiv.org/pdf/2602.16605
- Provenance: arxiv

## Abstract

A signed tree model of a graph $G$ is a compact binary structure consisting of a rooted binary tree whose leaves are bijectively mapped to the vertices of $G$, together with 2-colored edges $xy$, called transversal pairs, interpreted as bicliques or anti-bicliques whose sides are the leaves of the subtrees rooted at $x$ and at $y$. We design an algorithm that, given such a representation of an $n$-vertex graph $G$ with $p$ transversal pairs and a source $v \\in V(G)$, computes a shortest-path tree rooted at $v$ in $G$ in time $O(p \\log n)$. A wide variety of graph classes are such that for all $n$, their $n$-vertex graphs admit signed tree models with $O(n)$ transversal pairs: for instance, those of bounded symmetric difference, more generally of bounded sd-degeneracy, as well as interval graphs. As applications of our Single-Source Shortest Path algorithm and new techniques, we - improve the runtime of the fixed-parameter algorithm for first-order model checking on graphs given with a witness of low merge-width from cubic \[Dreier and Toruńczyk, STOC '25\] to quadratic; - give an $O(n^2 \\log n)$-time algorithm for All-Pairs Shortest Path (APSP) on graphs given with a witness of low merge-width, generalizing a result known on twin-width \[Twin-Width III, SICOMP '24\]; - extend and simplify an $O(n^2 \\log n)$-time algorithm for multiplying two $n \\times n$ matrices $A, B$ of bounded twin-width in \[Twin-Width V, STACS '23\]: now $A$ solely has to be an adjacency matrix of a graph of bounded twin-width and $B$ can be arbitrary; - give an $O(n^2 \\log^2 n)$-time algorithm for APSP on graphs of bounded twin-width, bypassing the need for contraction sequences in \[Twin-Width III, SICOMP '24; Bannach et al. STACS '24\]; - give an $O(n^{7/3} \\log^2 n)$-time algorithm for APSP on graphs of symmetric difference $O(n^{1/3})$.

_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.