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

• URL: http://arxiv.org/abs/2509.05129v1
• Date: Fri, 05 Sep 2025 14:14:36 GMT
• Title: Efficient Exact Resistance Distance Computation on Small-Treewidth Graphs: a Labelling Approach
• Authors: Meihao Liao, Yueyang Pan, Rong-Hua Li, Guoren Wang,
• Abstract summary: shortest-path distance computation achieves remarkable efficiency on small-treewidth graphs.<n>We propose treeindex, a novel index method that constructs a resistance distance labelling of size $O(n cdot h_mathcalG)$ in $O(n cdot h_mathcalG2 cdot d_max$.<n>Our labelling supports exact single-pair queries in $O(h_mathcalG)$ time and single-source queries in $O(n cdot h_math
• Score: 37.498311835613045
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• 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.

Related papers

• Efficiently Constructing Sparse Navigable Graphs [11.317292211864013]
  We present an $tildeO(n2)$ time algorithm for constructing an $O(log n)$-approximate sparsest navigable graph under any distance function.<n>We also show that our techniques can beat cubic time for the closely related and practically important problems of constructing $alpha$-shortcut reachable and $tau$-monotonic graphs.
  arXiv  Detail & Related papers  (2025-07-17T17:04:18Z)
• Approximating Optimal Labelings for Temporal Connectivity [7.394099294390271]
  We study the problem of scheduling the availability time of the edges of a temporal graph in such a way that all pairs of vertices are connected within a given maximum allowed time $a$.<n>The problem, known as emphMinimum Aged Labeling (MAL), has several applications in logistics, distribution scheduling, and information spreading in social networks.
  arXiv  Detail & Related papers  (2025-04-23T16:00:33Z)
• Graph Inference with Effective Resistance Queries [2.2349172369559156]
  We study graph inference using an oracle that returns the effective resistance (ER) between a pair of vertices.<n>Although it is known that an $n$-vertex graph can be uniquely reconstructed from all possible ER queries, little else is known.
  arXiv  Detail & Related papers  (2025-02-25T16:37:25Z)
• Graph Unfolding and Sampling for Transitory Video Summarization via Gershgorin Disc Alignment [48.137527345353625]
  User-generated videos (UGVs) uploaded from mobile phones to social media sites like YouTube and TikTok are short and non-repetitive. We summarize a transitory UGV into several discs in linear time via fast graph sampling based on Gershgorin disc alignment (GDA) We show that our algorithm achieves comparable or better video summarization performance compared to state-of-the-art methods, at a substantially reduced complexity.
  arXiv  Detail & Related papers  (2024-08-03T20:08:02Z)
• Matching the Statistical Query Lower Bound for $k$-Sparse Parity Problems with Sign Stochastic Gradient Descent [83.85536329832722]
  We solve the $k$-sparse parity problem with sign gradient descent (SGD) on two-layer fully-connected neural networks.<n>We show that this approach can efficiently solve the $k$-sparse parity problem on a $d$-dimensional hypercube.<n>We then demonstrate how a trained neural network with sign SGD can effectively approximate this good network, solving the $k$-parity problem with small statistical errors.
  arXiv  Detail & Related papers  (2024-04-18T17:57:53Z)
• Exact Algorithms and Lowerbounds for Multiagent Pathfinding: Power of Treelike Topology [0.0]
  We focus on efficiently finding paths for a set of $k agents on a given graph $G, where each agent seeks a path from its source to a target. An important measure of the quality of the solution is the length of the proposed schedule $ell$, that is, the length of a longest path. We show that MAPF is W[1]-hard for cliquewidth of $G$ plus $ell$ while it is FPT for treewidth of $G$ plus $ell$.
  arXiv  Detail & Related papers  (2023-12-15T09:42:46Z)
• Dynamic algorithms for k-center on graphs [3.568439282784197]
  We give the first efficient algorithms for the $k$-center problem on dynamic graphs undergoing edge updates. We show a reduction that leads to a fully dynamic $(2+epsilon)$-approximation algorithm for the $k$-center problem.
  arXiv  Detail & Related papers  (2023-07-28T13:50:57Z)
• Online Learning with Feedback Graphs: The True Shape of Regret [82.00098840619847]
  We prove that the minimax regret is proportional to $R*$ for any graph and time horizon $T$. Introducing an intricate exploration strategy, we define the mainAlgorithm algorithm that achieves the minimax optimal regret bound.
  arXiv  Detail & Related papers  (2023-06-05T15:35:00Z)
• Detection-Recovery Gap for Planted Dense Cycles [72.4451045270967]
  We consider a model where a dense cycle with expected bandwidth $n tau$ and edge density $p$ is planted in an ErdHos-R'enyi graph $G(n,q)$. We characterize the computational thresholds for the associated detection and recovery problems for the class of low-degree algorithms.
  arXiv  Detail & Related papers  (2023-02-13T22:51:07Z)
• Fast Graph Sampling for Short Video Summarization using Gershgorin Disc Alignment [52.577757919003844]
  We study the problem of efficiently summarizing a short video into several paragraphs, leveraging recent progress in fast graph sampling. Experimental results show that our algorithm achieves comparable video summarization as state-of-the-art methods, at a substantially reduced complexity.
  arXiv  Detail & Related papers  (2021-10-21T18:43:00Z)
• Random Subgraph Detection Using Queries [29.192695995340653]
  The planted densest subgraph detection problem refers to the task of testing whether in a given (random) graph there is a subgraph that is unusually dense. In this paper, we consider a natural variant of the above problem, where one can only observe a relatively small part of the graph using adaptive edge queries. For this model, we determine the number of queries necessary and sufficient (accompanied with a quasi-polynomial optimal algorithm) for detecting the presence of the planted subgraph.
  arXiv  Detail & Related papers  (2021-10-02T07:41:17Z)
• Approximating the Log-Partition Function [16.59989033959959]
  We provide an approach to quantify the approximation ratio through the property of the underlying graph structure. We provide a near lineartime variant that achieves an approximation ratio equal to the inverse of square-root of minimal effective resistance of the graph.
  arXiv  Detail & Related papers  (2021-02-19T22:57:32Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.