{"ID":2874255,"CreatedAt":"2026-06-01T04:54:23.091178241Z","UpdatedAt":"2026-06-01T04:54:23.091178241Z","DeletedAt":null,"paper_url":"https://arxiv.org/abs/2509.05129","arxiv_id":"2509.05129","title":"Efficient Exact Resistance Distance Computation on Small-Treewidth Graphs: a Labelling Approach","abstract":"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 \\cdot h_{\\mathcal{G}})$ in $O(n \\cdot h_{\\mathcal{G}}^2 \\cdot d_{\\max})$ time, where $h_{\\mathcal{G}}$ (tree height) and $d_{\\max}$ (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(h_{\\mathcal{G}})$ time and single-source queries in $O(n \\cdot h_{\\mathcal{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 (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.","short_abstract":"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...","url_abs":"https://arxiv.org/abs/2509.05129","url_pdf":"https://arxiv.org/pdf/2509.05129v1","authors":"[\"Meihao Liao\",\"Yueyang Pan\",\"Rong-Hua Li\",\"Guoren Wang\"]","published":"2025-09-05T14:14:36Z","proceeding":"cs.DB","tasks":"[\"cs.DB\",\"cs.DM\",\"cs.DS\",\"cs.LG\"]","methods":"[]","has_code":false}