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

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.