Abstract
Given a directed acyclic graph with non-negative edge-weights, two vertices s and t, and a threshold-weight L, we present a fully-polynomial time approximation-scheme for the problem of counting the s-t paths of length at most L. This is best possible, as we also show that the problem is #P-complete. We then show that, unless P=NP, there is no finite approximation to the bi-criteria version of the problem: count the number of s-t paths of length at most L (1) in the first criterion, and of length at most L (2) in the second criterion. On the positive side, we extend the approximation scheme for the relaxed version of the problem, where, given thresholds L (1) and L (2), we relax the requirement of the s-t paths to have length exactly at most L (1), and allow the paths to have length at most L (1') : = (1+delta)L (1), for any delta > 0.
Original language | English |
---|---|
Pages (from-to) | 45-59 |
Number of pages | 15 |
Journal | Theory of Computing Systems |
Volume | 58 |
Issue number | 1 |
DOIs | |
Publication status | Published - Jan 2016 |
Keywords
- Approximation algorithms
- Counting
- Shortest paths
- TANDEM MASS-SPECTROMETRY