Document Open Access Logo

Algorithms and Lower Bounds for Cycles and Walks: Small Space and Sparse Graphs

Authors Andrea Lincoln, Nikhil Vyas

PDF
Thumbnail PDF

File

LIPIcs.ITCS.2020.11.pdf
  • Filesize: 0.57 MB
  • 17 pages

Document Identifiers

Author Details

Andrea Lincoln
  • MIT, Cambridge, MA, USA
Nikhil Vyas
  • MIT, Cambridge, MA, USA

Funding

  • Lincoln, Andrea: Supported by NSF Grants CCF-1417238, CCF-1528078 and CCF-1514339, and BSF Grant BSF:2012338.
  • Vyas, Nikhil: Supported by an Akamai Presidential Fellowship, NSF Grant CCF-1552651 and CCF-1909429.

Cite AsGet BibTex

Andrea Lincoln and Nikhil Vyas. Algorithms and Lower Bounds for Cycles and Walks: Small Space and Sparse Graphs. In 11th Innovations in Theoretical Computer Science Conference (ITCS 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 151, pp. 11:1-11:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)
https://doi.org/10.4230/LIPIcs.ITCS.2020.11

Abstract

We consider space-efficient algorithms and conditional time lower bounds for finding cycles and walks in graphs. We give a reduction that connects the running time of undirected 2k-cycle to finding directed odd cycles, s-t connectivity in directed graphs, and Max-3-SAT. For example, we show that if 2k-cycle on O(n)-edge graphs can be solved in O(n^(1.5-ε)) time for some ε>0 then, a 2^(n(1-ε')) time algorithm exists for Max-3-SAT for some ε'>0. Additionally, we give a tight combinatorial lower bound for 2k-cycle detection, specifically when k is odd, of m^{2k/(k+1) +o(1)} given the Combinatorial k-Clique Hypothesis. On the algorithms side, we present a randomized algorithm for directed s-t connectivity using O(lg(n)^2) space and O(n^{lg(n)/2 + o(lg(n))}) expected time, giving a time improvement over Savitch’s famous algorithm, which takes at least n^{lg(n) - o(lg(n))} time. Under the conjecture that every O(lg(n)^2)-space algorithm for directed s-t connectivity requires n^Ω(lg(n)) time, we show that undirected 2k-cycle in O(lg(n)) space requires n^Ω(lg(k)) time.

Subject Classification

ACM Subject Classification
  • Theory of computation → Problems, reductions and completeness
  • Theory of computation → Graph algorithms analysis
Keywords
  • k-cycle
  • Space
  • Savitch
  • Sparse Graphs
  • Max-3-SAT

Metrics

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

References

  1. Amir Abboud, Arturs Backurs, and Virginia Vassilevska Williams. If the Current Clique Algorithms are Optimal, So is Valiant’s Parser. In IEEE 56th Annual Symposium on Foundations of Computer Science, FOCS 2015, Berkeley, CA, USA, 17-20 October, 2015, pages 98-117, 2015. URL: https://doi.org/10.1109/FOCS.2015.16.
  2. Noga Alon, Raphael Yuster, and Uri Zwick. Finding and Counting Given Length Cycles. Algorithmica, 17(3):209-223, 1997. URL: https://doi.org/10.1007/BF02523189.
  3. Noga Alon, Raphael Yuster, and Uri Zwick. Color Coding. In Encyclopedia of Algorithms, pages 335-338. Springer, 2016. URL: https://doi.org/10.1007/978-1-4939-2864-4_76.
  4. Greg Barnes, Jonathan F. Buss, Walter L. Ruzzo, and Baruch Schieber. A Sublinear Space, Polynomial Time Algorithm for Directed s-t Connectivity. SIAM J. Comput., 27(5):1273-1282, 1998. URL: https://doi.org/10.1137/S0097539793283151.
  5. Søren Dahlgaard, Mathias Bæk Tejs Knudsen, and Morten Stöckel. Finding even cycles faster via capped k-walks. In Proceedings of the 49th Annual ACM SIGACT Symposium on Theory of Computing, STOC 2017, Montreal, QC, Canada, June 19-23, 2017, pages 112-120, 2017. URL: https://doi.org/10.1145/3055399.3055459.
  6. François Le Gall. Powers of tensors and fast matrix multiplication. In International Symposium on Symbolic and Algebraic Computation, ISSAC '14, Kobe, Japan, July 23-25, 2014, pages 296-303, 2014. URL: https://doi.org/10.1145/2608628.2608664.
  7. Parikshit Gopalan, Richard J. Lipton, and Aranyak Mehta. Randomized Time-Space Tradeoffs for Directed Graph Connectivity. In Paritosh K. Pandya and Jaikumar Radhakrishnan, editors, FST TCS 2003: Foundations of Software Technology and Theoretical Computer Science, 23rd Conference, Mumbai, India, December 15-17, 2003, Proceedings, volume 2914 of Lecture Notes in Computer Science, pages 208-216. Springer, 2003. URL: https://doi.org/10.1007/978-3-540-24597-1_18.
  8. Richard C. Holt and Edward M. Reingold. On the time required to detect cycles and connectivity in graphs. Mathematical systems theory, 6(1):103-106, March 1972. URL: https://doi.org/10.1007/BF01706081.
  9. Richard M. Karp. Reducibility Among Combinatorial Problems. In Proceedings of a symposium on the Complexity of Computer Computations, held March 20-22, 1972, at the IBM Thomas J. Watson Research Center, Yorktown Heights, New York, USA, pages 85-103, 1972. URL: https://doi.org/10.1007/978-1-4684-2001-2_9.
  10. Andrea Lincoln, Virginia Vassilevska Williams, and R. Ryan Williams. Tight Hardness for Shortest Cycles and Paths in Sparse Graphs. In Proceedings of the Twenty-Ninth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2018, New Orleans, LA, USA, January 7-10, 2018, pages 1236-1252, 2018. Google Scholar
  11. Benjamin Rossman. Formulas vs. circuits for small distance connectivity. In Symposium on Theory of Computing, STOC 2014, New York, NY, USA, May 31 - June 03, 2014, pages 203-212, 2014. Google Scholar
  12. Walter J. Savitch. Relationships Between Nondeterministic and Deterministic Tape Complexities. J. Comput. Syst. Sci., 4(2):177-192, 1970. URL: https://doi.org/10.1016/S0022-0000(70)80006-X.
  13. Dieter van Melkebeek and Gautam Prakriya. Derandomizing Isolation in Space-Bounded Settings. SIAM J. Comput., 48(3):979-1021, 2019. URL: https://doi.org/10.1137/17M1130538.
  14. Avi Wigderson. The Complexity of Graph Connectivity. In Mathematical Foundations of Computer Science 1992, 17th International Symposium, MFCS'92, Prague, Czechoslovakia, August 24-28, 1992, Proceedings, pages 112-132, 1992. Google Scholar
  15. Virginia Vassilevska Williams. Multiplying matrices faster than coppersmith-winograd. In Proceedings of the 44th Symposium on Theory of Computing Conference, STOC 2012, New York, NY, USA, May 19 - 22, 2012, pages 887-898, 2012. URL: https://doi.org/10.1145/2213977.2214056.
  16. Virginia Vassilevska Williams. On some fine-grained questions in algorithms and complexity. In Proceedings of the International Congress of Mathematicians, page to appear, 2018. Google Scholar
  17. Raphael Yuster and Uri Zwick. Finding Even Cycles Even Faster. SIAM J. Discrete Math., 10(2):209-222, 1997. URL: https://doi.org/10.1137/S0895480194274133.
  18. Raphael Yuster and Uri Zwick. Detecting Short Directed Cycles Using Rectangular Matrix Multiplication and Dynamic Programming. In Proceedings of the Fifteenth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA '04, pages 254-260, Philadelphia, PA, USA, 2004. Society for Industrial and Applied Mathematics. URL: http://dl.acm.org/citation.cfm?id=982792.982828.
  19. Uri Zwick. All pairs shortest paths using bridging sets and rectangular matrix multiplication. J. ACM, 49(3):289-317, 2002. URL: https://doi.org/10.1145/567112.567114.
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 Imprint Privacy Contact