Tight Lower Bounds for Directed Cut Sparsification and Distributed Min-Cut
Authors: 
Yu Cheng, Max Li, Honghao Lin, Zi-Yi Tai, David P. Woodruff, Jason ZhangAuthors Info & Claims
Article No.: 85, Pages 1 - 18
Abstract
In this paper, we consider two fundamental cut approximation problems on large graphs. We prove new lower bounds for both problems that are optimal up to logarithmic factors.
The first problem is approximating cuts in balanced directed graphs. In this problem, we want to build a data structure that can provide (1 ± ε)-approximation of cut values on a graph with n vertices. For arbitrary directed graphs, such a data structure requires Ω(n2) bits even for constant ε. To circumvent this, recent works study β-balanced graphs, meaning that for every directed cut, the total weight of edges in one direction is at most β times the total weight in the other direction. We consider the for-each model, where the goal is to approximate each cut with constant probability, and the for-all model, where all cuts must be preserved simultaneously. We improve the previous Ømega(n √β/ε) lower bound in the for-each model to ~Ω (n √β /ε) and we improve the previous Ω(n β/ε) lower bound in the for-all model to Ω(n β/ε2). This resolves the main open questions of (Cen et al., ICALP, 2021).
The second problem is approximating the global minimum cut in a local query model, where we can only access the graph via degree, edge, and adjacency queries. We prove an ΩL(min m, m/ε2 k R) lower bound for this problem, which improves the previous ΩL(m/k R) lower bound, where m is the number of edges, k is the minimum cut size, and we seek a (1+ε)-approximation. In addition, we show that existing upper bounds with minor modifications match our lower bound up to logarithmic factors.
References
[1]
Ahn, K. J., Guha, S., and McGregor, A. Graph sketches: sparsification, spanners, and subgraphs. In Proceedings of the 31st ACM SIGMOD-SIGACT-SIGART Symposium on Principles of Database Systems (PODS) (2012), pp. 5--14.
[2]
Andoni, A., Chen, J., Krauthgamer, R., Qin, B., Woodruff, D. P., and Zhang, Q. On sketching quadratic forms. In Proceedings of the 2016 ACM Conference on Innovations in Theoretical Computer Science (ITCS) (2016), pp. 311--319.
[3]
Batson, J. D., Spielman, D. A., and Srivastava, N. Twice-Ramanujan sparsifiers. SIAM J. Comput. 41, 6 (2012), 1704--1721.
[4]
Benczúr, A. A., and Karger, D. R. Approximating s-t minimum cuts in Õ(n2) time. In Proceedings of the 28th Annual ACM Symposium on the Theory of Computing (STOC) (1996), ACM, pp. 47--55.
[5]
Bishnu, A., Ghosh, A., Mishra, G., and Paraashar, M. Query complexity of global minimum cut. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM) (2021), vol. 207 of Leibniz International Proceedings in Informatics (LIPIcs), pp. 6:1--6:15.
[6]
Carlson, C., Kolla, A., Srivastava, N., and Trevisan, L. Optimal lower bounds for sketching graph cuts. In Proceedings of the 30th Annual ACM-SIAM Symposium on Discrete Algorithms(SODA) (2019), pp. 2565--2569.
[7]
Cen, R., Cheng, Y., Panigrahi, D., and Sun, K. Sparsification of directed graphs via cut balance. In 48th International Colloquium on Automata, Languages, and Programming (ICALP) (2021), vol. 198 of LIPIcs, pp. 45:1--45:21.
[8]
Eden, T., and Rosenbaum, W. Lower bounds for approximating graph parameters via communication complexity. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM) (2018), vol. 116 of Leibniz International Proceedings in Informatics (LIPIcs), pp. 11:1--11:18.
[9]
Ene, A., Miller, G. L., Pachocki, J., and Sidford, A. Routing under balance. In Proceedings of the 48th Annual ACM SIGACT Symposium on Theory of Computing (STOC) (2016), pp. 598--611.
[10]
Fung, W. S., Hariharan, R., Harvey, N. J. A., and Panigrahi, D. A general framework for graph sparsification. SIAM J. Comput. 48, 4 (2019), 1196--1223.
[11]
Ikeda, M., and Tanigawa, S. Cut sparsifiers for balanced digraphs. In Approximation and Online Algorithms - 16th International Workshop (WAOA) (2018), vol. 11312 of Lecture Notes in Computer Science, pp. 277--294.
[12]
Kapralov, M., and Panigrahy, R. Spectral sparsification via random spanners. In Innovations in Theoretical Computer Science (ITCS) (2012), pp. 393--398.
[13]
Kremer, I., Nisan, N., and Ron, D. Errata for: "on randomized one-round communication complexity". Comput. Complex. 10, 4 (2001), 314--315.
[14]
Lee, Y. T., and Sun, H. An SDP-based algorithm for linear-sized spectral sparsification. In Proceedings of the 49th Annual ACM SIGACT Symposium on Theory of Computing (STOC) (2017), pp. 678--687.
[15]
McGregor, A. Graph stream algorithms: a survey. ACM SIGMOD Record 43, 1 (2014), 9--20.
[16]
Rubinstein, A., Schramm, T., and Weinberg, S. M. Computing exact minimum cuts without knowing the graph. In 9th Innovations in Theoretical Computer Science Conference (ITCS) (2018), vol. 94 of LIPIcs, pp. 39:1--39:16.
[17]
Spielman, D. A., and Srivastava, N. Graph sparsification by effective resistances. SIAM J. Comput. 40, 6 (2011), 1913--1926.
[18]
Spielman, D. A., and Teng, S. Nearly-linear time algorithms for graph partitioning, graph sparsification, and solving linear systems. In Proceedings of the 36th Annual ACM Symposium on Theory of Computing (STOC) (2004), pp. 81--90.
[19]
Spielman, D. A., and Teng, S. Spectral sparsification of graphs. SIAM J. Comput. 40, 4 (2011), 981--1025.
[20]
Woodruff, D. P., and Zhang, Q. An optimal lower bound for distinct elements in the message passing model. In Proceedings of the 25th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA) (2014), p. 718--733.
Index Terms
- Tight Lower Bounds for Directed Cut Sparsification and Distributed Min-Cut
Recommendations
Faster Cut Sparsification of Weighted Graphs
AbstractA cut sparsifier is a reweighted subgraph that maintains the weights of the cuts of the original graph up to a multiplicative factor of . This paper considers computing cut sparsifiers of weighted graphs of size . Our algorithm ...
Unifying Maximum Cut and Minimum Cut of a Planar Graph
The real-weight maximum cut of a planar graph is considered. Given an undirected planar graph with real-value weights associated with its edges, the problem is to find a partition of the vertices into two nonempty sets such that the sum of the weights ...
On the cut polyhedron
For an undirected connected graph G, the cut polyhedron cut(G) is the dominant of the convex hull of the incidence vectors of all nonempty edge cutsets of G. We give some properties of the facial structure of cut(G). In particular, we characterize all ...
Comments
Please enable JavaScript to view thecomments powered by Disqus.Information & Contributors
Information
Published In
May 2024
852 pages
Copyright © 2024 ACM.
Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than the author(s) must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected].
Publisher
Association for Computing Machinery
New York, NY, United States
Publication History
Published: 14 May 2024
Published in PACMMOD Volume 2, Issue 2
Author Tags
Qualifiers
- Research-article
Funding Sources
- NSF Award
- National Institute of Health
Contributors
Other Metrics
Bibliometrics & Citations
Bibliometrics
Article Metrics
- 0Total Citations
- 149Total Downloads
- Downloads (Last 12 months)149
- Downloads (Last 6 weeks)45
Reflects downloads up to 28 Nov 2024
Other Metrics
Citations
View Options
Login options
Check if you have access through your login credentials or your institution to get full access on this article.
Sign in