Graph Problems Tight Bounds

Tight Bounds for Graph Problems in Insertion Streams Xiaoming Sun and David P. Woodruff Chinese Academy of Sciences and IBM Research-Almaden

Streaming Models 4 3 7 3 1 1 2 Long sequence of items appear one-by-one numbers, points, edges, (usually) adversarially ordered one pass over the stream Goal: approximate a function of the underlying stream use small amount of space (in bits) Efficiency: usually necessary for algorithms to be both randomized and approximate

Graph Streams See a stream of edges e = {i,j} defining a graph G on n nodes Example problems: decide if G is connected, bipartite, or planar. Approximate the minimum cut size, etc. Most problems have an (n) bit space lower bound Many problems have an n poly(log n) bit upper bound A significant savings over a na ve ?2bit upper bound Question: what is the optimal space complexity of these problems? Is it (n) bits? (n log n) bits? Or n poly(log n) bits?

Comparison to Other Problems Many asymptotically tight bounds are known in streaming approximating distinct elements, entropy, norms linear regression, approximate matrix product For basic graph questions, such as connectivity: O(n log n) bit upper bound (maintain a spanning forest) (n) bit lower bound (reduction from set disjointness) Could it be that there is an O(n) bit upper bound using a clever, possibly adaptive hashing scheme to store the edge identities?

Our Results Tight lower bounds for a number of graph problems Connectivity (n log n) bits Planarity and H-minor freeness (n log n) bits Bipartiteness (n log n) bits Cycle-freeness, Eulerian testing, testing if a sparse graph has bounded diameter, finding a minimum spanning tree all require (n log n) bits k-Edge Connectivity Any deterministic algorithm requires (nk log n) bits k-Vertex Connectivity Any deterministic algorithm allowing multi-edges requires (nk log n) bits

Our Results Continued Another popular model is the dynamic graph model, in which edges can be inserted and deleted We show an (n log2n) bit lower bound for approximating the minimum cut up to a constant factor Implies an (n (log n) log W) bound for computing cut or spectral sparsifiers of a graph in dynamic graphs with edge weights bounded by W Batson, Spielman, Srivastava give an O(n (log n + log log W)) bit sparsifier Our result is the first dynamic graph stream lower bound larger than the size of a sparsifier Upper bounds in a dynamic stream are O(nlog4n) or O(nlog5n) (see work by Ahn, Guha, McGregor and Kapralov, Lee, Musco, Musco, Sidford)

Talk Outline 1. Permutation-Based Communication Complexity Problems 2. Tight lower bound for Graph Connectivity 3. Lower bound for approximating the minimum cut in dynamic graph streams

Streaming Lower Bounds via Communication Complexity b 2 {0,1}n Create stream s(b) a 2 {0,1}n Create stream s(a) Lower Bound Technique 1. Run Streaming Alg on s(a), transmit state of Alg(s(a)) to Bob 2. Bob computes Alg(s(a), s(b)) 3. If Bob solves g(a,b), space complexity of Alg at least the 1- way communication complexity of g

Connectivity There is an (n log n) bit lower bound for deterministic protocols for connectivity (Dowling and Wilson) The randomized communication complexity is not known We show the randomized 1-way communication complexity is (n log n) bits To do so, we introduce a few permutation-problems

Perm Problem M ? 0,1? log ? ? [?log?] Alice is given a permutation of 1, 2, , n represented as a redundant (n log n)-bit vector (1), (2), , (n) Bob is given an index i in [n log n ] = {1, 2, , n log n} Alice sends a single message M to Bob Bob should output the i-th bit of with probability > 2/3

AugmentedPerm Problem M i [nlogn] j logn j+1, , log n 1, , log n 0,1n log n Alice has log n permutations Bob should output the i-th bit of j with constant probability Bob also knows j+1, , log n

Lower Bound for Perm Uses information theory Recall for random variables X, Y, the mutual information I X ;Y = H X H X Y) H(X) bitlength(X) Let = 1, , n log n be a uniformly random permutation By the chain rule, I( 1, , n log n ; M) = iI i ; M 1, , i 1) = iH i 1, , i 1) H( i | 1, , i 1,M) = H iH( i | 1, , i 1,M) log n! (nlogn)H( ), where the inequality is Fano s, and uses the correctness of the protocol Setting the failure probability small enough gives an n log n lower bound Similar argument gives n log2n lower bound for AugmentedPerm

Talk Outline 1. Permutation-Based Communication Complexity Problems 2. Tight lower bound for Graph Connectivity 3. Lower bound for approximating the minimum cut in dynamic graph streams

Connectivity Reduction k ? ? specifies a random matching in a bipartite graph with n nodes in each part Bob is interested in the -th bit of k for some k and , determined by i Graph is connected if and only if -th bit of k is 1

Talk Outline 1. Permutation-Based Communication Complexity Problems 2. Tight lower bound for Graph Connectivity 3. Lower bound for approximating the minimum cut in dynamic graph streams

Lower Bound for Approximate MinCut 100 10 10log ? 100 10 10log ? 10log ? 10 100 100 10 10log ? 2 log n 1 Alice sends all duplicate edges to Bob (there are O(log2?) such edges whp) Alice runs the streaming algorithm on the union of the log n matchings Bob has i and knows j+1, , log n Bob deletes all edges in the graphs corresponding to j+1 , , log n Bob is interested in the -th bit of jk for some k and , determined by i

Lower Bound for Approximate MinCut 10j 10j 10j k 10j For a given node, it has j edges from matchings 1, 2, , j The edges are weighted 10,102, ,10? If the the -th bit of jk is 0, minimum cut is at most 2(10 + 100 + + 10j 1) Otherwise, minimum cut value is at least 10j

Open Questions 1. k-edge connectivity lower bound holds only for deterministic algorithms. For randomized we only get a kn lower bound can this be improved? 2. k-vertex connectivity lower bound holds only for deterministic algorithms which can process multi-edges. Can these assumptions be removed? 3. For graph sparsifiers and minimum cut, our lower bound is only (n log2?) while the upper bound is O(n log4 n) can this gap be closed? 4. For connectivity in dynamic streams, the upper bound is O(nlog3n) and our (n log n) lower bound is all that is known can this gap be closed?

Lower Bound for AugmentedPerm Let ?1, ,?log ?be independent and uniformly random permutations By the chain rule, j;M 1 j, , i 1 j I 1, , log n; M = i,jI i , j+1 , , log n ) j 1 j, , i 1 j j 1 j, , i 1 j = i,jH i = H 1, , log n i,jH i j+1 , , log n , M) j+1 , , log n ) H i j 1 j, , i 1 j j+1 , , log n ,M) n!log n (nlog2n)H( ), log where the inequality is Fano s, and uses the correctness of the protocol Setting the failure probability small enough gives an nlog2n lower bound