# Efficient Exact Resistance Distance Computation on Small-Treewidth Graphs: a Labelling Approach

arXiv: https://arxiv.org/abs/2509.05129 · HTML: https://mlsanity.com/paper/2509.05129/

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- Builds on 22 of its 68 references that are in the map.
- First posted on arXiv 5 Sep 2025.

## Builds on (most cited first, 22 of 22)

- [Understanding over-squashing and bottlenecks on graphs via curvature](https://mlsanity.com/paper/2111.14522/) (2021)
- [Approximate Gaussian Elimination for Laplacians: Fast, Sparse, and Simple](https://mlsanity.com/paper/1605.02353/) (2016)
- [Graph Clustering using Effective Resistance](https://mlsanity.com/paper/1711.06530/) (2017)
- [Ultrasparse Ultrasparsifiers and Faster Laplacian System Solvers](https://mlsanity.com/paper/2011.08806/) (2020)
- [Fast Exact Shortest-Path Distance Queries on Large Networks by Pruned Landmark Labeling](https://mlsanity.com/paper/1304.4661/) (2013)
- [Local Algorithms for Estimating Effective Resistance](https://mlsanity.com/paper/2106.03476/) (2021)
- [Robust and Practical Solution of Laplacian Equations by Approximate Elimination](https://mlsanity.com/paper/2303.00709/) (2023)
- [Efficient Estimation of Pairwise Effective Resistance](https://mlsanity.com/paper/2312.06123/) (2023)
- [Fast link prediction for large networks using spectral embedding](https://mlsanity.com/paper/1703.09693/) (2017)
- [Effective Resistances in Non-Expander Graphs](https://mlsanity.com/paper/2307.01218/) (2023)
- [A New Approach to Estimating Effective Resistances and Counting Spanning Trees in Expander Graphs](https://mlsanity.com/paper/2211.01468/) (2022)
- [Hierarchical Cut Labelling -- Scaling Up Distance Queries on Road Networks](https://mlsanity.com/paper/2311.11063/) (2023)
- [Stable Tree Labelling for Accelerating Distance Queries on Dynamic Road Networks](https://mlsanity.com/paper/2501.17379/) (2025)
- [Hop Doubling Label Indexing for Point-to-Point Distance Querying on Scale-Free Networks](https://mlsanity.com/paper/1403.0779/) (2014)
- [Sublinear Distance Labeling](https://mlsanity.com/paper/1507.02618/) (2015)
- [Hopsets with Constant Hopbound, and Applications to Approximate Shortest Paths](https://mlsanity.com/paper/1605.04538/) (2016)
- [Beyond Highway Dimension: Small Distance Labels Using Tree Skeletons](https://mlsanity.com/paper/1609.00512/) (2016)
- [Algorithmic and Hardness Results for the Hub Labeling Problem](https://mlsanity.com/paper/1611.06605/) (2016)
- [Fast and Compact Exact Distance Oracle for Planar Graphs](https://mlsanity.com/paper/1702.03259/) (2017)
- [A Combinatorial Cut-Toggling Algorithm for Solving Laplacian Linear Systems](https://mlsanity.com/paper/2010.16316/) (2020)
- [A Simple and Efficient Parallel Laplacian Solver](https://mlsanity.com/paper/2304.14345/) (2023)
- [Dual-Hierarchy Labelling: Scaling Up Distance Queries on Dynamic Road Networks](https://mlsanity.com/paper/2506.18013/) (2025)

## Built on by (most cited first, 1 of 1)

- [Bridging Local and Global Knowledge: Cascaded Mixture-of-Experts Learning for Near-Shortest Path Routing](https://mlsanity.com/paper/2603.15541/) (2026)

## Abstract (arXiv)

Resistance distance computation is a fundamental problem in graph analysis, yet existing random walk-based methods are limited to approximate solutions and suffer from poor efficiency on small-treewidth graphs (e.g., road networks). In contrast, shortest-path distance computation achieves remarkable efficiency on such graphs by leveraging cut properties and tree decompositions. Motivated by this disparity, we first analyze the cut property of resistance distance. While a direct generalization proves impractical due to costly matrix operations, we overcome this limitation by integrating tree decompositions, revealing that the resistance distance r(s,t) depends only on labels along the paths from s and t to the root of the decomposition. This insight enables compact labelling structures. Based on this, we propose treeindex, a novel index method that constructs a resistance distance labelling of size O(n · hG) in O(n · hG2 · dmax) time, where hG (tree height) and dmax (maximum degree) behave as small constants in many real-world small-treewidth graphs (e.g., road networks). Our labelling supports exact single-pair queries in O(hG) time and single-source queries in O(n · hG) time. Extensive experiments show that TreeIndex substantially outperforms state-of-the-art approaches. For instance, on the full USA road network, it constructs a 405 GB labelling in 7 hours (single-threaded) and answers exact single-pair queries in 10-3 seconds and single-source queries in 190 seconds--the first exact method scalable to such large graphs.