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 smalltreewidth 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 𝑟 (𝑠, 𝑡) depends only on labels along the paths from 𝑠 and 𝑡 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 𝑂 (𝑛 • ℎ G ) in 𝑂 (𝑛 •ℎ 2 G •𝑑 max ) time, where ℎ G (tree height) and 𝑑 max (maximum degree) behave as small constants in many real-world small-treewidth graphs (e.g., road networks). Our labelling supports exact singlepair queries in 𝑂 (ℎ G ) time and single-source queries in 𝑂 (𝑛 • ℎ G ) 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 (singlethreaded) 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.