Document Open Access Logo

Sparsification of Directed Graphs via Cut Balance

Authors Ruoxu Cen, Yu Cheng, Debmalya Panigrahi, Kevin Sun

PDF

File

Thumbnail PDF
PDF
LIPIcs.ICALP.2021.45.pdf
  • Filesize: 0.81 MB
  • 21 pages

Document Identifiers

Related Versions

Subject Classification

ACM Subject Classification
  • Theory of computation → Sparsification and spanners
Keywords
  • Graph sparsification
  • directed graphs
  • cut sketches
  • space complexity

Metrics

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

Abstract

In this paper, we consider the problem of designing cut sparsifiers and sketches for directed graphs. To bypass known lower bounds, we allow the sparsifier/sketch to depend on the balance of the input graph, which smoothly interpolates between undirected and directed graphs. We give nearly matching upper and lower bounds for both for-all (cf. Benczúr and Karger, STOC 1996) and for-each (Andoni et al., ITCS 2016) cut sparsifiers/sketches as a function of cut balance, defined the maximum ratio of the cut value in the two directions of a directed graph (Ene et al., STOC 2016). We also show an interesting application of digraph sparsification via cut balance by using it to give a very short proof of a celebrated maximum flow result of Karger and Levine (STOC 2002).

Cite As Get BibTex

Ruoxu Cen, Yu Cheng, Debmalya Panigrahi, and Kevin Sun. Sparsification of Directed Graphs via Cut Balance. In 48th International Colloquium on Automata, Languages, and Programming (ICALP 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 198, pp. 45:1-45:21, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021) https://doi.org/10.4230/LIPIcs.ICALP.2021.45

Author Details

Ruoxu Cen
  • Duke University, Durham, NC, USA
Yu Cheng
  • University of Illinois at Chicago, IL, USA
Debmalya Panigrahi
  • Duke University, Durham, NC, USA
Kevin Sun
  • Duke University, Durham, NC, USA

Funding

Debmalya Panigrahi and Kevin Sun: This work was supported in part by NSF grants CCF-1535972, CCF-1955703, and an NSF CAREER Award CCF-1750140.

Acknowledgements

Part of the work was done while Yu Cheng was visiting the Institute for Advanced Study.

References

  1. Kook Jin Ahn and Sudipto Guha. Graph sparsification in the semi-streaming model. In International Colloquium on Automata, Languages, and Programming, pages 328-338. Springer, 2009. Google Scholar
  2. Kook Jin Ahn, Sudipto Guha, and Andrew McGregor. Analyzing graph structure via linear measurements. In Proceedings of the Twenty-Third ACM-SIAM Symposium on Discrete Algorithms, pages 459-467, 2012. Google Scholar
  3. Kook Jin Ahn, Sudipto Guha, and Andrew McGregor. Graph sketches: sparsification, spanners, and subgraphs. In Proceedings of the 31st ACM Symposium on Principles of Database Systems, pages 5-14, 2012. Google Scholar
  4. Kook Jin Ahn, Sudipto Guha, and Andrew McGregor. Spectral sparsification in dynamic graph streams. In Proceedings of the 16th International Workshop on Approximation Algorithms for Combinatorial Optimization Problems and the 17th International Workshop on Randomization and Computation, pages 1-10, 2013. Google Scholar
  5. Zeyuan Allen Zhu, Zhenyu Liao, and Lorenzo Orecchia. Spectral sparsification and regret minimization beyond matrix multiplicative updates. In Proceedings of the 47th ACM Symposium on Theory of Computing, pages 237-245, 2015. Google Scholar
  6. Alexandr Andoni, Jiecao Chen, Robert Krauthgamer, Bo Qin, David P Woodruff, and Qin Zhang. On sketching quadratic forms. In Proceedings of the 2016 ACM Conference on Innovations in Theoretical Computer Science, pages 311-319. ACM, 2016. Google Scholar
  7. Joshua Batson, Daniel A Spielman, and Nikhil Srivastava. Twice-Ramanujan sparsifiers. SIAM Journal on Computing, 41(6):1704-1721, 2012. Google Scholar
  8. András A Benczúr and David R Karger. Randomized approximation schemes for cuts and flows in capacitated graphs. SIAM Journal on Computing, 44(2):290-319, 2015. Google Scholar
  9. Dietmar Berwanger, Anuj Dawar, Paul Hunter, Stephan Kreutzer, and Jan Obdržálek. The DAG-width of directed graphs. Journal of Combinatorial Theory, Series B, 102(4):900-923, 2012. Google Scholar
  10. Charles Carlson, Alexandra Kolla, Nikhil Srivastava, and Luca Trevisan. Optimal lower bounds for sketching graph cuts. In Proceedings of the 30th ACM-SIAM Symposium on Discrete Algorithms, pages 2565-2569, 2019. Google Scholar
  11. Timothy Chu, Yu Gao, Richard Peng, Sushant Sachdeva, Saurabh Sawlani, and Junxing Wang. Graph sparsification, spectral sketches, and faster resistance computation, via short cycle decompositions. In Proceedings of the 59th IEEE Annual Symposium on Foundations of Computer Science, pages 361-372, 2018. Google Scholar
  12. Fan Chung. Laplacians and the cheeger inequality for directed graphs. Annals of Combinatorics, 9(1):1-19, 2005. Google Scholar
  13. Michael B. Cohen, Jonathan Kelner, Rasmus Kyng, John Peebles, Richard Peng, Anup B. Rao, and Aaron Sidford. Solving directed Laplacian systems in nearly-linear time through sparse LU factorizations. In Proceedings of the 59th IEEE Symposium on Foundations of Computer Science, pages 898-909, 2018. Google Scholar
  14. Michael B. Cohen, Jonathan Kelner, John Peebles, Richard Peng, Anup B. Rao, Aaron Sidford, and Adrian Vladu. Almost-linear-time algorithms for Markov chains and new spectral primitives for directed graphs. In Proceedings of the 49th ACM Symposium on Theory of Computing, pages 410-419, 2017. Google Scholar
  15. Alina Ene, Gary Miller, Jakub Pachocki, and Aaron Sidford. Routing under balance. In Proceedings of the forty-eighth annual ACM symposium on Theory of Computing, pages 598-611. ACM, 2016. Google Scholar
  16. Lester Randolph Ford and Delbert R Fulkerson. Maximal flow through a network. Canadian journal of Mathematics, 8:399-404, 1956. Google Scholar
  17. Wai Shing Fung, Ramesh Hariharan, Nicholas JA Harvey, and Debmalya Panigrahi. A general framework for graph sparsification. In Proceedings of the forty-third annual ACM symposium on Theory of computing, pages 71-80. ACM, 2011. Google Scholar
  18. Ashish Goel, Michael Kapralov, and Sanjeev Khanna. Graph sparsification via refinement sampling. CoRR, abs/1004.4915, 2010. URL: http://arxiv.org/abs/1004.4915.
  19. Paul Hunter and Stephan Kreutzer. Digraph measures: Kelly decompositions, games, and orderings. Theoretical Computer Science, 399(3):206-219, 2008. Google Scholar
  20. Motoki Ikeda and Shin-ichi Tanigawa. Cut sparsifiers for balanced digraphs. In International Workshop on Approximation and Online Algorithms, pages 277-294. Springer, 2018. Google Scholar
  21. Arun Jambulapati and Aaron Sidford. Efficient Õ(n/ε) spectral sketches for the Laplacian and its pseudoinverse. In Proceedings of the 29th ACM-SIAM Symposium on Discrete Algorithms, pages 2487-2503, 2018. Google Scholar
  22. Thor Johnson, Neil Robertson, Paul D Seymour, and Robin Thomas. Directed tree-width. Journal of Combinatorial Theory, Series B, 82(1):138-154, 2001. Google Scholar
  23. Michael Kapralov, Yin Tat Lee, Cameron Musco, Christopher Musco, and Aaron Sidford. Single pass spectral sparsification in dynamic streams. SIAM J. Comput., 46(1):456-477, 2017. Google Scholar
  24. Michael Kapralov, Aida Mousavifar, Cameron Musco, Christopher Musco, and Navid Nouri. Faster spectral sparsification in dynamic streams. CoRR, abs/1903.12165, 2019. URL: http://arxiv.org/abs/1903.12165.
  25. Michael Kapralov, Navid Nouri, Aaron Sidford, and Jakab Tardos. Dynamic streaming spectral sparsification in nearly linear time and space. CoRR, abs/1903.12150, 2019. URL: http://arxiv.org/abs/1903.12150.
  26. Michael Kapralov and Rina Panigrahy. Spectral sparsification via random spanners. In Innovations in Theoretical Computer Science 2012, Cambridge, MA, USA, January 8-10, 2012, pages 393-398, 2012. Google Scholar
  27. David R Karger and Matthew S Levine. Random sampling in residual graphs. In Proceedings of the thiry-fourth annual ACM symposium on Theory of computing, pages 63-66. ACM, 2002. Google Scholar
  28. David R Karger and Clifford Stein. A new approach to the minimum cut problem. Journal of the ACM (JACM), 43(4):601-640, 1996. Google Scholar
  29. Dmitry Kogan and Robert Krauthgamer. Sketching cuts in graphs and hypergraphs. In Proceedings of the 2015 Conference on Innovations in Theoretical Computer Science, pages 367-376, 2015. Google Scholar
  30. Ioannis Koutis, Alex Levin, and Richard Peng. Improved spectral sparsification and numerical algorithms for SDD matrices. In 29th International Symposium on Theoretical Aspects of Computer Science, pages 266-277, 2012. Google Scholar
  31. Ioannis Koutis, Gary L. Miller, and Richard Peng. Approaching optimality for solving SDD linear systems. In Proceedings of the 51th Annual IEEE Symposium on Foundations of Computer Science, pages 235-244, 2010. Google Scholar
  32. Ioannis Koutis, Gary L. Miller, and Richard Peng. A nearly-m log n time solver for SDD linear systems. In Proceedings of the 52nd IEEE Symposium on Foundations of Computer Science, pages 590-598, 2011. Google Scholar
  33. Rasmus Kyng, Yin Tat Lee, Richard Peng, Sushant Sachdeva, and Daniel A. Spielman. Sparsified Cholesky and multigrid solvers for connection laplacians. In Proceedings of the 48th ACM Symposium on Theory of Computing, pages 842-850, 2016. Google Scholar
  34. Yin Tat Lee and He Sun. Constructing linear-sized spectral sparsification in almost-linear time. In Proceedings of the 56th IEEE Symposium on Foundations of Computer Science, pages 250-269, 2015. Google Scholar
  35. Yin Tat Lee and He Sun. An SDP-based algorithm for linear-sized spectral sparsification. In Proceedings of the 49th ACM Symposium on Theory of Computing, pages 678-687, 2017. Google Scholar
  36. Henry Lin. Reducing directed max flow to undirected max flow. Unpublished Manuscript, 2009. Google Scholar
  37. Adam W Marcus, Daniel A Spielman, and Nikhil Srivastava. Interlacing families II: Mixed characteristic polynomials and the kadison—singer problem. Annals of Mathematics, pages 327-350, 2015. Google Scholar
  38. Ilan Newman and Yuri Rabinovich. On multiplicative Lambda-approximations and some geometric applications. SIAM J. Comput., 42(3):855-883, 2013. Google Scholar
  39. Jan Obdržálek. DAG-width: connectivity measure for directed graphs. In Proceedings of the seventeenth annual ACM-SIAM symposium on Discrete algorithm, pages 814-821, 2006. Google Scholar
  40. Jonah Sherman. Nearly maximum flows in nearly linear time. In Proceedings of the 54th Annual IEEE Symposium on Foundations of Computer Science, pages 263-269, 2013. Google Scholar
  41. Tasuku Soma and Yuichi Yoshida. Spectral sparsification of hypergraphs. In Proceedings of the 13th ACM-SIAM Symposium on Discrete Algorithms, pages 2570-2581, 2019. Google Scholar
  42. Daniel A Spielman and Nikhil Srivastava. Graph sparsification by effective resistances. SIAM Journal on Computing, 40(6):1913-1926, 2011. Google Scholar
  43. Daniel A. Spielman and Shang-Hua Teng. Spectral sparsification of graphs. SIAM Journal on Computing, 40(4):981-1025, 2011. Google Scholar
  44. Ying Zhang, Zhiqiang Zhao, and Zhuo Feng. Towards scalable spectral sparsification of directed graphs. In Proceedings of the 15th IEEE International Conference on Embedded Software and Systems, pages 1-2, 2019. Google Scholar
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-2025 Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact