{"id":"arxiv:2602.16605","kind":"preprint","title":"Fast Shortest Path in Graphs With Sparse Signed Tree Models and Applications","authors":["Édouard Bonnet","Colin Geniet","Eun Jung Kim","Sungmin Moon"],"author_count":4,"year":2026,"published":"2026-02-18","venue":null,"cited_by":null,"doi":null,"arxiv_id":"2602.16605","nct_id":null,"source_url":"https://arxiv.org/abs/2602.16605","archive_url":"https://space-kitty.com/papers/arxiv:2602.16605","updated":"2026-02-18","pmid":null,"pmcid":null,"openalex_id":null,"pdf_url":"https://arxiv.org/pdf/2602.16605","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_license":"CC0-1.0 (arXiv descriptive metadata)","license":null,"is_open_access":false,"retracted":false,"peer_reviewed":false,"categories":["cs.DS","cs.DM","math.CO"],"details":null,"provenance":"arxiv","attribution":"Abstract: arXiv descriptive metadata (CC0). Thank you to arXiv for use of its open access interoperability. This service was not reviewed or approved by, nor does it necessarily express or reflect the policies or opinions of, arXiv.","topics":[],"cited_in_dossiers":[]}