An FPTAS for Computing the Distribution Function of the Longest Path Length in DAGs with Uniformly Distributed Edge Lengths
An FPTAS for Computing the Distribution Function of the Longest Path Length in DAGs with Uniformly Distributed Edge Lengths
复制标题
DOI：
10.1007/978-3-319-53925-6_33
复制
发表时间：
2017-03
期刊：
影响因子：
--
通讯作者：
Ei Ando
中科院分区：
文献类型：
--
作者：
Ei Ando
Given a directed acyclic graph (DAG)withnvertices andmedges, we consider random edge lengths. That is, as the input, we have $${{{{\varvec{a}}}}}\in \mathbb {Z}_{>0}^{m}$$, whose components are given for each edges. Then, the random lengthof edgeeis a mutually independent random variable that obeys a uniform distribution on. In this paper, we consider the probability that the longest path length is at most a certain value, which is equal to the probability that all paths inGhave length at mostx. The problem can be considered as the computation of anm-dimensional polytope $$K_G({{{{\varvec{a}}}}},x)$$ that is a hypercube truncated by exponentially many hyperplanes that are as many as the number of paths inG. This problem is-hard even ifGis a directed path. In this paper, motivated by the recent technique of deterministic approximation of-hard problems, we show that there is adeterministicFPTAS for the problem of computing $$\mathrm{Vol}(K_G({{{{\varvec{a}}}}},x))$$ if the pathwidth ofGis bounded by a constantp. Our algorithm outputs a valuesatisfying that $$1\le V'/\mathrm{Vol}(K_G({{{{\varvec{a}}}}},x)) \le 1+\epsilon $$ and finishes intime, whereLis the number of bits in the input. If the pathwidthpis a constant, the running time is.
Given a directed acyclic graph (DAG)withnvertices andmedges, we consider random edge lengths. That is, as the input, we have $${{{{\varvec{a}}}}}\in \mathbb {Z}_{>0}^{m}$$, whose components are given for each edges. Then, the random lengthof edgeeis a mutually independent random variable that obeys a uniform distribution on. In this paper, we consider the probability that the longest path length is at most a certain value, which is equal to the probability that all paths inGhave length at mostx. The problem can be considered as the computation of anm-dimensional polytope $$K_G({{{{\varvec{a}}}}},x)$$ that is a hypercube truncated by exponentially many hyperplanes that are as many as the number of paths inG. This problem is-hard even ifGis a directed path. In this paper, motivated by the recent technique of deterministic approximation of-hard problems, we show that there is adeterministicFPTAS for the problem of computing $$\mathrm{Vol}(K_G({{{{\varvec{a}}}}},x))$$ if the pathwidth ofGis bounded by a constantp. Our algorithm outputs a valuesatisfying that $$1\le V'/\mathrm{Vol}(K_G({{{{\varvec{a}}}}},x)) \le 1+\epsilon $$ and finishes intime, whereLis the number of bits in the input. If the pathwidthpis a constant, the running time is.