The Complexity of Computing Path Length Distributions with Edges i.i.d. Random via Local Uniformity
2026-07-11 • Computational Complexity
Computational ComplexityComputational Geometry
AI summaryⓘ
The authors study how to find the chance that the shortest or longest path in a directed graph has a certain length when edge lengths are random. They show this problem is very hard (#P-hard), even if edge lengths follow common random distributions like uniform or normal. They also find that if the graph has a specific structure called low treewidth, the problem can be solved more efficiently. For uniform edge lengths, the authors create a new method using dynamic programming and tree decompositions that runs in a reasonable time for graphs with small treewidth.
Directed graphShortest pathLongest pathRandom edge lengthsUniform distribution#P-hardnessTreewidthDynamic programmingTree decompositionConvolution
Authors
Ei Ando
Abstract
We investigate the problem of computing the distribution function for the shortest and longest path lengths in a directed graph with random edge lengths. Specifically, when these lengths are uniformly distributed, the problem reduces to computing the volume of a polytope defined by the graph structure. We establish that the problem is $\#P$-hard, even under the restricted condition that the random edge lengths are identically and independently distributed (i.i.d.) according to any continuous probability distribution with certain natural conditions, the local uniformity. This hardness result applies broadly: while the uniform distribution provides an essential case for the reduction, other distributions -- such as exponential or normal -- are similarly hard because they contain uniform distributions in every arbitrarily small interval. Furthermore, we show that the problem is contained within $\mathrm{XP}$ with respect to the treewidth $k$ of the underlying undirected graph. For the specific case of i.i.d. uniform edge lengths, we present a novel dynamic programming algorithm that processes a tree decomposition by iteratively performing convolutions to propagate distribution functions. Our approach achieves a time complexity of $n^{O(k^2)}$ for any fixed treewidth $k$.