The Distribution Function of the Longest Path Length in Constant Treewidth DAGs with Random Edge Length

This paper is about the length $X_{\mathrm{M}\mathrm{A}\mathrm{X}}$ of the longest path in directed acyclic graph (DAG) $G=(V,E)$ with random edge lengths, where $\mathrm{\mid }V\mathrm{\mid }=n$ and $\mathrm{\mid }E\mathrm{\mid }=m$. When the edge lengths are mutually independent and uniformly distributed, the problem of computing the distribution function $\Pr[X_{\rm MAX}\le x]$isknowntobe$#$P-hardevenincase$G$ is a directed path. In this case, $\mathrm{Pr}[X_{\mathrm{M}\mathrm{A}\mathrm{X}}\le 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 $\mathrm{Pr}[X_{\mathrm{M}\mathrm{A}\mathrm{X}}\le x]$ in case the treewidth of $G$ is at most a constant $k$. The running time of our algorithm is $O(k^{2}n(\frac{16(k+1)m{n}^2}{ϵ}{)}^{4k^2+6k+2})$ to achieve a multiplicative approximation ratio $1+ϵ$. Before our FPTAS, we present a fundamental formula that represents $\mathrm{Pr}[X_{\mathrm{M}\mathrm{A}\mathrm{X}}\le 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 $\mathrm{Pr}[X_{\mathrm{M}\mathrm{A}\mathrm{X}}\le x]$ is fixed parameter tractable if we choose treewidth $k$, the additive error ${ϵ}^{\mathrm{\prime }}$, and $x$ as the parameters.