nach oben

Theory of Computing Systems

Erschienen in:

01.01.2016

Approximately Counting Approximately-Shortest Paths in Directed Acyclic Graphs

verfasst von: Matúš Mihalák, Rastislav Šrámek, Peter Widmayer

Erschienen in: Theory of Computing Systems | Ausgabe 1/2016

Einloggen

Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.

search-config

KI-gestützte Suche

Aus

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 ₁ in the first criterion, and of length at most L ₂ in the second criterion. On the positive side, we extend the approximation scheme for the relaxed version of the problem, where, given thresholds L ₁ and L ₂, we relax the requirement of the s-t paths to have length exactly at most L ₁, and allow the paths to have length at most L _1′ : = (1+δ)L ₁, for any δ > 0.

Vorheriger Artikel Improved Approximation Algorithm for k-level Uncapacitated Facility Location Problem (with Penalties)

Nächster Artikel Degree-Constrained Graph Orientation: Maximum Satisfaction and Minimum Violation

Sie haben noch keine Lizenz? Dann Informieren Sie sich jetzt über unsere Produkte:

Springer Professional "Wirtschaft+Technik"

Online-Abonnement

Mit Springer Professional "Wirtschaft+Technik" erhalten Sie Zugriff auf:

über 102.000 Bücher
über 537 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Finance + Banking
Management + Führung
Marketing + Vertrieb
Maschinenbau + Werkstoffe
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

Jetzt informieren

Springer Professional "Wirtschaft"

Online-Abonnement

Mit Springer Professional "Wirtschaft" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 340 Zeitschriften

aus folgenden Fachgebieten:

Bauwesen + Immobilien
Business IT + Informatik
Finance + Banking
Management + Führung
Marketing + Vertrieb
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

Jetzt informieren

Springer Professional "Technik"

Online-Abonnement

Mit Springer Professional "Technik" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 390 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Maschinenbau + Werkstoffe

Jetzt Wissensvorsprung sichern!

Jetzt informieren

Note that due to the lack of cycles, the problems of looking for shortest and longest paths on DAGs are computationally identical.

To see this, observe that in a topologically sorted graph G, any subset of V∖{s,t} gives a unique candidate for an s-t path.

Broder, A.Z., Mayr, E.W.: Counting minimum weight spanning trees. J. Algorithm. 24, 171–176 (1997)MATHMathSciNetCrossRef

Buhmann, J.M., Mihalák, M., Šrámek, R., Widmayer, P.: Robust optimization in the presence of uncertainty. In: Proceedings of the 4th Conference on Innovations in Theoretical Computer Sciencei (ITCS). pp. 505–514. ACM, New York (2013)

Burge, C., Karlin, S.: Prediction of complete gene structures in human genomic DNA. J. Mol. Biol. 268(1), 78–94 (1997)CrossRef

Chen, T., Kao, M.Y., Tepel, M., Rush, J., Church, G.M.: A dynamic programming approach to de novo peptide sequencing via tandem mass spectrometry. J. Comput. Biol. 8(3), 325–337 (2001)CrossRef

Durbin, R., Eddy, S.R., Krogh, A., Mitchison, G.: Biological Sequence Analysis: Probabilistic Models of Proteins and Nucleic Acids. Cambridge University Press (1998)

Dyer, M., Frieze, A., Kannan, R., Kapoor, A., Perkovic, L., Vazirani, U.: A mildly exponential time algorithm for approximating the number of solutions to a multidimensional knapsack problem. Comb. Probab. Comput. 2(3), 271–284 (1993)MATHMathSciNetCrossRef

Gopalan, P., Klivans, A., Meka, R., Štefankovič, D., Vempala, S., Vigoda, E.: An FPTAS for # knapsack and related counting problems. In: Proceedings of the 52nd Annual IEEE Symposium on Foundations of Computer Science (FOCS). pp. 817–826 (2011)

Jerrum, M.: Two-dimensional monomer-dimer systems are computationally intractable. J. Stat. Phys. 48(1–2), 121–134 (1987)MathSciNetCrossRef

Karp, R.M.: Reducibility Among Combinatorial Problems. Springer (1972)

10.

Kreher, D.L., Stinson, D.R.: Combinatorial Algorithms: Generation, Enumeration, and Search (1998)

11.

Lu, B., Chen, T.: A suboptimal algorithm for de novo peptide sequencing via tandem mass spectrometry. J. Comput. Biol. 10(1), 1–12 (2003)CrossRef

12.

Naor, D., Brutlag, D.: On suboptimal alignments of biological sequences. In: Proceedings of the 4th Annual Symposium on Combinatorial Pattern Matching (CPM). pp. 179–196. Springer (1993)

13.

Rizzi, R., Tomescu, A.I.: Combinatorial decomposition approaches for efficient counting and random generation fptases. CoRR abs/1307.2347v2 (2013)

14.

Štefankovič, D., Vempala, S., Vigoda, E.: A deterministic polynomial-time approximation scheme for counting knapsack solutions. SIAM J. Comput. 41(2), 356–366 (2012)MATHMathSciNetCrossRef

15.

Valiant, L.G.: The complexity of computing the permanent. Theor. Comput. Sci. 8(2), 189–201 (1979)MATHMathSciNetCrossRef

16.

Valiant, L.G.: The complexity of enumeration and reliability problems. SIAM J. Comput. 8(3), 410–421 (1979)MATHMathSciNetCrossRef

Titel: Approximately Counting Approximately-Shortest Paths in Directed Acyclic Graphs
verfasst von: Matúš Mihalák
Rastislav Šrámek
Peter Widmayer
Publikationsdatum: 01.01.2016
Verlag: Springer US
Erschienen in: Theory of Computing Systems / Ausgabe 1/2016
Print ISSN: 1432-4350
Elektronische ISSN: 1433-0490
DOI: https://doi.org/10.1007/s00224-014-9571-7

Springer Professional

Abstract

Bitte loggen Sie sich ein, um Zugang zu Ihrer Lizenz zu erhalten.

Sie haben noch keine Lizenz? Dann Informieren Sie sich jetzt über unsere Produkte:

Springer Professional "Wirtschaft+Technik"

Springer Professional "Wirtschaft"

Springer Professional "Technik"

Weitere Artikel der Ausgabe 1/2016

Improved Approximation Algorithm for k-level Uncapacitated Facility Location Problem (with Penalties)

On Fixed Cost k-Flow Problems

Approximating the Sparsest k-Subgraph in Chordal Graphs

Min-Sum 2-Paths Problems

Online Knapsack Revisited

Foreword of the Special Issue Dedicated to the 2013 Workshop on Approximation and Online Algorithms

Premium Partner