The Complexity of Computing Path Length Distributions with Edges i.i.d. Random via Local Uniformity

Jul 16, 2026

Upload by Quinn

The paper studies how to compute distribution functions for the shortest and longest path lengths in a directed graph with random edge lengths. Under uniformly distributed lengths, the task becomes computing the volume of a polytope determined by the graph structure. The problem is shown to be #P-hard even when edge lengths are i.i.d. from any continuous distribution satisfying local uniformity. The work also proves containment in XP parameterized by treewidth and gives a dynamic programming algorithm for i.i.d. uniform edges.

LanguageEnglish

CategoryResearch & Report

FormatPDF

Pages40

Reading Time1 h 41 min

Introduction

Motivation and background

Computational complexity foundations

Path Length Distributions with Locally Uniform Edge Lengths

Reduction to polytope volume

Prior hardness and approximation limits

Main results and algorithmic approach

Complexity classification via treewidth

Dynamic programming for i.i.d. uniform edges

arXiv :2607 . 10 195v 1 [ cs .CC] 11 Jul 2026 The Complexity of Computing Path Length Distributions with Edges i.i.d. Random via Local Uniformity Ei ANDO \# Senshu University, 2-1-1, Higashimita, Tama-Ku, Kawasaki, Kanagawa, Japan ~~ 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 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 nO (k2 ) for any fixed treewidth k. 2012 ACM Subject Classification Theory of computation → Shortest paths; Theory of computation → Problems, reductions and completeness; Mathematics of computing → Distribution functions Keywords and phrases \#P-hardness, shortest path, longest path, random edge length, distribution function, local uniformity, treewidth, XP Funding Ei ANDO : 1 Introduction Motivation and Background. Computing the distribution function of the longest path length with random edge lengths presents a fundamental challenge in Statistical Static Timing Analysis (SSTA) for VLSI design. In modern semiconductor manufacturing, timing violations arising from process variations are a primary source of yield loss and carry significant economic consequences. Since deterministic analysis fails to capture these stochastic behaviors due to constant scaling in semiconductor devices, the performance of a logic circuit should be modeled using its full path length distribution. While numerous approximation algorithms have been proposed assuming continuous delays [7, 11, 33], and the necessity of such stochastic modeling is well-documented [34], the problem remains formidable. Indeed, even modern statistical approaches, including machine learning methods, are actively being explored, as noted in recent surveys like [19] . The computational challenge predates the VLSI era, finding its roots in Operations Research with the Performance Evaluation and Review Technique (PERT), introduced by Malcolm, Roseboom, Clark, and Fazar [25] . PERT models project duration as the longest path length within a Directed Acyclic Graph (DAG), where individual task durations are modeled using random variables. Over the decades, significant scholarly attention has been dedicated to determining the distribution functions of both shortest and longest paths, resulting in various heuristic and bounding methods (e.g., Adlakha and Kulkarni [1]; Ludwig, Möhring, and Stork [24]) . The computational complexity of these path length distribution problems is rooted in the class \#P, which was first defined by Valiant [31] to characterize the intractability in counting and reliability problems [32] . Initial work on stochastic networks demonstrated that computing both shortest and 2 Path Length Distributions with Locally Uniform Edge Lengths longest path length distributions is NP-hard (Ball and Provan [5]) . Subsequently, Hagstrom [17] established the \#P-completeness of the problem when edge

FAQs

What distributions does the paper focus on?

It focuses on computing distribution functions for the shortest and longest path lengths in a directed graph with random edge lengths.

Why does the uniform case become a polytope-volume computation?

When edge lengths are continuously uniformly distributed, the longest path length distribution reduces to computing the volume of a high-dimensional polytope defined by the graph structure.

What is the complexity status under i.i.d. continuous edge lengths?

The problem is proved #P-hard even when edge lengths are i.i.d. according to any continuous distribution satisfying local uniformity, and it is also shown to belong to XP with respect to treewidth.

Jul 16, 2026

Upload by Quinn