Deterministic space limits found for streaming graph clique and independent set
Deterministic Streaming Lower Bounds for Approximate Maximum Clique and Maximum Independent Set
Data Structures and Algorithms
Summary
Finding large groups of connected or unconnected points in a network is important but can be hard with limited memory when the network changes quickly. The authors show that if you don’t use randomness, then you need significantly more memory to get good approximate answers in a single pass through the data. They proved this by linking it to a fundamental communication problem. Their results highlight how randomness helps save memory in these streaming graph problems.
What this means in practice
- •For streaming algorithm designers: Understand the lower limits on memory needed without randomness when approximating cliques or independent sets in large evolving networks.
- •For distributed system engineers: Determine when randomness is necessary to efficiently compute near-optimal groups in network data viewed as streams.
A theory result. No direct application yet.
Authors
Adithya Diddapur
Abstract
We study the canonical \textsf{Maximum Clique} and \textsf{Maximum Independent Set} problems in the one-pass edge-arrival graph streaming setting. Here, the edges of some input graph $G = (V,E)$ are presented one at a time (possibly including deletions), before an algorithm needs to produce either a large clique or independent set at the end of the stream, with the focus being on space complexity. We are interested in finding $β$-approximate solutions, for any $β\geq 1$. Previous work gave an algorithm using $\tilde{O}\left(n^2/β^2\right)$ bits of space, together with a corresponding $\tildeΩ\left(n^2/β^2\right)$ two-party communication lower bound [Halldórsson et al., ICALP'12], seeming to resolve the problem. However, their algorithm crucially relies on randomness, and the best known deterministic algorithm remains a folklore derandomisation using $O\left(n^2/β\right)$ bits of space, leaving a (deterministic) gap of size $\tilde{O}(β)$. We resolve this deterministic gap with an (almost) tight lower bound: any deterministic algorithm for either problem must use $Ω\left(\frac{n^2}{β\cdot\log n}\right)$ bits of space. Our proof is via a two-party one-way communication lower bound, and highlights the power of randomness when approaching either of these problems.