Streaming Lower Bounds for Approximating MAX-CUT

DOI10.1137/1.9781611973730.84MaRDI QIDQ5363106zbMATH OpenOpenAlexFDO

Authors Michael Kapralov, Sanjeev Khanna, Madhu Sudan

Publication date 5 October 2017

Published in Proceedings of the Twenty-Sixth Annual ACM-SIAM Symposium on Discrete Algorithms (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1409.2138

Mathematics Subject Classification ID

Graph algorithms (graph-theoretic aspects) (05C85) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10) Approximation algorithms (68W25) Online algorithms; streaming algorithms (68W27)

Abstract: We consider the problem of estimating the value of max cut in a graph in the streaming model of computation. At one extreme, there is a trivial $2$-approximation for this problem that uses only $O(logn)$ space, namely, count the number of edges and output half of this value as the estimate for max cut value. On the other extreme, if one allows $ildeO(n)$ space, then a near-optimal solution to the max cut value can be obtained by storing an $ildeO(n)$-size sparsifier that essentially preserves the max cut. An intriguing question is if poly-logarithmic space suffices to obtain a non-trivial approximation to the max-cut value (that is, beating the factor $2$). It was recently shown that the problem of estimating the size of a maximum matching in a graph admits a non-trivial approximation in poly-logarithmic space. Our main result is that any streaming algorithm that breaks the $2$-approximation barrier requires $ildeOmega(sqrtn)$ space even if the edges of the input graph are presented in random order. Our result is obtained by exhibiting a distribution over graphs which are either bipartite or $frac12$-far from being bipartite, and establishing that $ildeOmega(sqrtn)$ space is necessary to differentiate between these two cases. Thus as a direct corollary we obtain that $ildeOmega(sqrtn)$ space is also necessary to test if a graph is bipartite or $frac12$-far from being bipartite. We also show that for any $epsilon>0$, any streaming algorithm that obtains a $(1+epsilon)$-approximation to the max cut value when edges arrive in adversarial order requires $n^{1-O(epsilon)}$ space, implying that $Omega(n)$ space is necessary to obtain an arbitrarily good approximation to the max cut value.

Recommendations

• Intractability of min- and max-cut in streaming graphs
• On the approximability of Max-Cut
• An optimal space lower bound for approximating MAX-CUT
• Approximate Max-Flow Min-(Multi)Cut Theorems and Their Applications
• Near-optimal approximation algorithm for simultaneous Max-Cut
• An O(log k) Approximate Min-Cut Max-Flow Theorem and Approximation Algorithm
• Linear-Time Approximation Algorithms for the Max Cut Problem
• Approximate max-integral-flow/min-multicut theorems
• Streaming complexity of approximating Max 2CSP and Max Acyclic Subgraph
• Time bounds for streaming problems

Cited in

(21)

• New bounds for the CLIQUE-GAP problem using graph decomposition theory
• Dynamic graph stream algorithms in \(o(n)\) space
• Intractability of min- and max-cut in streaming graphs
• Streaming and communication complexity of clique approximation
• New bounds for the CLIQUE-GAP problem using graph decomposition theory
• Sketching cuts in graphs and hypergraphs
• scientific article; zbMATH DE number 6905172 (Why is no real title available?)
• (1 + (1))-approximation to MAX-CUT requires linear space
• Streaming complexity of approximating Max 2CSP and Max Acyclic Subgraph
• Sublinear algorithms for MAXCUT and correlation clustering
• Fast Distributed Approximation for Max-Cut
• Testable bounded degree graph properties are random order streamable
• An optimal space lower bound for approximating MAX-CUT
• scientific article; zbMATH DE number 5182608 (Why is no real title available?)
• scientific article; zbMATH DE number 7650072 (Why is no real title available?)
• (Noisy) gap cycle counting strikes back: random order streaming lower bounds for connected components and beyond
• Streaming approximation resistance of every ordering CSP
• Matrix hypercontractivity, streaming algorithms and LDCs: the large alphabet case
• Sketching approximability of all finite CSPs
• Maximum coverage in the data stream model: parameterized and generalized
• Streaming algorithms for network design

This page was built for publication: Streaming Lower Bounds for Approximating MAX-CUT

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5363106)