2019/10/22 by Ei Ando, Ando, Ei
Computer Science · Mathematics · #Advanced Graph Theory Research #Complexity and Algorithms in Graphs #Computational Complexity (cs.CC) #Computational Geometry and Mesh Generation #Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences #FOS: Mathematics #Probability (math.PR) #cs.CC #cs.DS #math.PR
paper · pdf · doi:10.48550/arxiv.1910.09791
40 pages, 2 figures
openalex publication_date 2019/10/22 · openalex created_date 2019/11/01 · arxiv created 2022/03/27 · arxiv updated 2022/03/29 · openalex updated_date 2026/07/28
This paper is about the length X\rm MAX of the longest path in directed acyclic graph (DAG) G=(V,E) with random edge lengths, where |V|=n and |E|=m. When the edge lengths are mutually independent and uniformly distributed, the problem of computing the distribution function Pr[X\rm MAX≤ x] is known to be #P-hard even in case G is a directed path. In this case, Pr[X\rm MAX≤ x] is equal to the volume of the knapsack polytope, an m-dimensional unit hypercube truncated by a halfspace. In this paper, we show that there is a deterministic fully polynomial time approximation scheme (FPTAS) for computing Pr[X\rm MAX≤ x] in case the treewidth of G is at most a constant k. The running time of our algorithm is O(k2 n(\frac16(k+1)mn2ε)4k2+6k+2) to achieve a multiplicative approximation ratio 1+ε. Before our FPTAS, we present a fundamental formula that represents Pr[X\rm MAX≤ x] by at most n-1 repetitions of definite integrals. Moreover, in case the edge lengths follow the mutually independent standard exponential distribution, we show a ((4k+2)mn)O(k) time exact algorithm. For random edge lengths satisfying certain conditions, we also show that computing Pr[X\rm MAX≤ x] is fixed parameter tractable if we choose treewidth k, the additive error ε', and x as the parameters.