Document Open Access Logo

A Streaming Algorithm for the Undirected Longest Path Problem

Authors Lasse Kliemann, Christian Schielke, Anand Srivastav

PDF
Thumbnail PDF

File

LIPIcs.ESA.2016.56.pdf
  • Filesize: 0.59 MB
  • 17 pages

Document Identifiers

Author Details

Lasse Kliemann
Christian Schielke
Anand Srivastav

Cite As Get BibTex

Lasse Kliemann, Christian Schielke, and Anand Srivastav. A Streaming Algorithm for the Undirected Longest Path Problem. In 24th Annual European Symposium on Algorithms (ESA 2016). Leibniz International Proceedings in Informatics (LIPIcs), Volume 57, pp. 56:1-56:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2016) https://doi.org/10.4230/LIPIcs.ESA.2016.56

Abstract

We present the first streaming algorithm for the longest path problem in undirected graphs. The input graph is given as a stream of edges and RAM is limited to only a linear number of edges at a time (linear in the number of vertices n). We prove a per-edge processing time of O(n), where a naive solution would have required Omega(n^2). Moreover, we give a concrete linear upper bound on the number of bits of RAM that are required.
 
On a set of graphs with various structure, we experimentally compare our algorithm with three leading RAM algorithms: Warnsdorf (1823), Pohl-Warnsdorf (1967), and Pongrasz (2012). Although conducting only a small constant number of passes over the input, our algorithm delivers competitive results: with the exception of preferential attachment graphs, we deliver at least 71% of the solution of the best RAM algorithm. The same minimum relative performance of 71% is observed over all graph classes after removing the 10% worst cases. This comparison has strong meaning, since for each instance class there is one algorithm that on average delivers at least 84% of a Hamilton path. In some cases we deliver even better results than any of the RAM algorithms.

Subject Classification

Keywords
  • Streaming Algorithms
  • Undirected Longest Path Problem
  • Graph Algorithms
  • Combinatorial Optimization

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads
    0
    Metadata Views

References

  1. Noga Alon, Raphael Yuster, and Uri Zwick. Color-coding. Journal of the ACM, 42(4):844-856, 1995. URL: http://dx.doi.org/10.1145/210332.210337.
  2. Ziv Bar-Yossef, Ravi Kumar, and D. Sivakumar. Reductions in streaming algorithms, with an application to counting triangles in graphs. In Proceedings of the 13th Annual ACM-SIAM Symposium on Discrete Algorithms, San Francisco, CA, USA, January 2002 (SODA 2002), pages 623-632, 2002. URL: http://dl.acm.org/citation.cfm?id=545464.
  3. Albert-László Barabási and Réka Albert. Emergence of scaling in random networks. Science, 286(5439):509-512, 1999. URL: http://dx.doi.org/10.1126/science.286.5439.509.
  4. Cristina Bazgan, Miklos Santha, and Zsolt Tuza. On the approximation of finding a(nother) Hamiltonian cycle in cubic Hamiltonian graphs. Journal of Algorithms, 31(1):249-268, 1999. Conference version at STACS 1998. URL: http://dx.doi.org/10.1006/jagm.1998.0998.
  5. Andreas Björklund. Determinant sums for undirected Hamiltonicity. SIAM Journal on Computing, 43(1):280-299, 2014. Conference version at FOCS 2010. URL: http://dx.doi.org/10.1137/110839229.
  6. Andreas Björklund and Thore Husfeldt. Finding a path of superlogarithmic length. SIAM Journal on Computing, 32(6):1395-1402, 2003. URL: http://dx.doi.org/10.1137/S0097539702416761.
  7. Andreas Björklund, Thore Husfeldt, Petteri Kaski, and Mikko Koivisto. Narrow sieves for parameterized paths and packings, 2010. URL: http://arxiv.org/abs/1007.1161.
  8. Andreas Björklund, Thore Husfeldt, and Sanjeev Khanna. Approximating longest directed paths and cycles. In Proceedings of the 31st International Colloquium on Automata, Languages and Programming, Turku, Finland, July 2004 (ICALP 2004), pages 222-233, 2004. URL: http://dx.doi.org/10.1007/978-3-540-27836-8_21.
  9. Hans L. Bodlaender. On linear time minor tests with depth-first search. Journal of Algorithms, 14:1-23, 1993. Conference version at WADS 1989. URL: http://dx.doi.org/10.1006/jagm.1993.1001.
  10. R.W. Bulterman, F.W. van der Sommen, G. Zwaan, T. Verhoeff, A.J.M. van Gasteren, and W.H.J. Feijen. On computing a longest path in a tree. Information Processing Letters, 81(2):93-96, 2002. URL: http://dx.doi.org/10.1016/S0020-0190(01)00198-3.
  11. Tomás Feder, Rajeev Motwani, and Carlos Subi. Approximating the longest cycle problem in sparse graphs. SIAM Journal on Computing, 31(5):1596-1607, 2002. URL: http://dx.doi.org/10.1137/S0097539701395486.
  12. Joan Feigenbaum, Sampath Kannan, Andrew McGregor, Siddharath Suri, and Jian Zhang. On graph problems in a semi-streaming model. Theoretical Computer Science, 348:207-216, 2005. Conference version at ICALP 2004. URL: http://dx.doi.org/10.1016/j.tcs.2005.09.013.
  13. Joan Feigenbaum, Sampath Kannan, Andrew McGregor, Siddharath Suri, and Jian Zhang. Graph distances in the data-stream model. SIAM Journal on Computing, 38:1709–1727, 2008. URL: http://dx.doi.org/10.1137/070683155.
  14. Harold N. Gabow. Finding paths and cycles of superpolylogarithmic length. SIAM Journal on Computing, 36(6):1648-1671, 2007. URL: http://dx.doi.org/10.1137/S0097539704445366.
  15. Harold N. Gabow and Shuxin Nie. Finding long paths, cycles and circuits. In Proceedings of the 19th International Symposium on Algorithms and Computation, Gold Coast, Australia, December 2008 (ISAAC 2008), pages 752-753, 2008. URL: http://dx.doi.org/10.1007/978-3-540-92182-0_66.
  16. Venkatesan Guruswami and Krzysztof Onak. Superlinear lower bounds for multipass graph processing. Electronic Colloquium on Computational Complexity, 2014. Conference version at CCC 2013. URL: http://eccc.hpi-web.de/report/2013/002/.
  17. David Karger, Rajeev Motwani, and G.D.S. Ramkumar. On approximating the longest path in a graph. Algorithmica, 18:82-98, 1997. URL: http://dx.doi.org/10.1007/BF02523689.
  18. Fatemeh Keshavarz-Kohjerdia, Alireza Bagherib, and Asghar Asgharian-Sardroudb. A linear-time algorithm for the longest path problem in rectangular grid graphs. Discrete Applied Mathematics, 160(3):210-217, 2012. URL: http://dx.doi.org/10.1016/j.dam.2011.08.010.
  19. Ioannis Koutis. Faster algebraic algorithms for path and packing problems. In Proceedings of the 35th International Colloquium on Automata, Languages and Programming, Reykjavik, Iceland, July 2008 (ICALP 2008), pages 575-586, 2008. URL: http://dx.doi.org/10.1007/978-3-540-70575-8_47.
  20. Dmitri Krioukov, Fragkiskos Papadopoulos, Maksim Kitsak, Amin Vahdat, and Marián Boguñá. Hyperbolic geometry of complex networks. Physical Review E, 82, 2010. URL: http://dx.doi.org/10.1103/PhysRevE.82.036106.
  21. Minko Markov, Mugurel Ionuţ Andreica, Krassimir Manev, and Nicolae Ţăpuş. A linear time algorithm for computing longest paths in cactus graphs. Serdica Journal of Computing, 6(3), 2012. URL: http://serdica-comp.math.bas.bg/index.php/serdicajcomputing/article/view/158.
  22. Burkhard Monien. How to find long paths efficiently. Annals of Discrete Mathematics, 25:239-254, 1985. URL: https://digital.ub.uni-paderborn.de/hs/content/titleinfo/42079.
  23. Muthu Muthukrishnan. Data streams: Algorithms and applications. Foundations and Trends in Theoretical Computer Science, 1(2):67 pages, 2005. URL: http://algo.research.googlepages.com/eight.ps.
  24. Ira Pohl. A method for finding Hamilton paths and knight’s tours. Communications of the ACM, 10(7):446-449, 1967. URL: http://dx.doi.org/10.1145/363427.363463.
  25. Ira Pohl and Larry Stockmeyer. Pohl-Warnsdorf - revisited. In Proceedings of the International Conference on Intelligent Systems and Control, Honolulu, Hawaii, USA, August 2004 (ISC 2004), 2004. URL: https://users.soe.ucsc.edu/~pohl/Papers/Pohl_Stockmeyer_full.pdf.
  26. Lajos L. Pongrácz. A greedy approximation algorithm for the longest path problem in undirected graphs, 2012. URL: http://arxiv.org/abs/1209.2503v2.
  27. Robert Sedgewick and Kevin Wayne. Algorithms. Addison-Wesley Professional, 2011. Google Scholar
  28. Ryuhei Uehara and Yushi Uno. On computing longest paths in small graph classes. International Journal of Foundations of Computer Science, 18(5), 2007. URL: http://dx.doi.org/10.1142/S0129054107005054.
  29. Sundar Vishwanathan. An approximation algorithm for finding long paths in Hamiltonian graphs. Journal of Algorithms, 50(2):246–256, 2004. Conference version at SODA 2000. URL: http://dx.doi.org/10.1016/S0196-6774(03)00093-2.
  30. Moritz von Looz, Christian L. Staudt, Henning Meyerhenke, and Roman Prutkin. Fast generation of complex networks with underlying hyperbolic geometry, 2015. URL: http://arxiv.org/abs/1501.03545.
  31. Duncan J. Watts and Steven H. Strogatz. Collective dynamics of ’small-world' networks. Nature, 393:440-442, 1998. URL: http://dx.doi.org/10.1038/30918.
  32. Ryan Williams. Finding paths of length k in O^*(2^k) time. Information Processing Letters, 109:315-318, 2009. URL: http://dx.doi.org/10.1016/j.ipl.2008.11.004.
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact