PaperlayerView exact revision on arXiv

Source-linked AI summary

Deterministic Streaming Lower Bounds for Approximate Maximum Clique and Maximum Independent Set

Adithya Diddapur

arXiv:2609.18635v1cs.DS

TL;DR

The paper addresses the open deterministic gap in one-pass streaming approximation for Maximum Clique and Maximum Independent Set. It develops a lower-bound construction, including an edge-removal adaptation for independent sets, and reports that its lower bound nearly matches the folklore deterministic algorithm, highlighting the power of randomness.

  • Problem

    Whether the deterministic gap in streaming approximation for Maximum Clique and Maximum Independent Set can be closed remains open.

    Source: §1 · p. 2

  • Method

    For Maximum Independent Set, the construction removes the edges assigned to Alice and Bob so prior cliques correspond to independent sets.

    Source: §4.1 · p. 20

  • Results

    The authors report a strong lower bound that makes the folklore derandomised algorithm almost optimal.

    Source: §1.1 · p. 3

  • Takeaways & Limitations

    The result makes explicit the power of randomisation for both Maximum Clique and Maximum Independent Set.

    Source: §1.1 · p. 3

    The compression-step argument assumes the message is a deterministic function of EA, which itself depends on A.

    Source: §3.1.2 · p. 12

Abstract

from arXiv · show

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 $\beta$-approximate solutions, for any $\beta \geq 1$. Previous work gave an algorithm using $\tilde{O}\left(n^2/\beta^2\right)$ bits of space, together with a corresponding $\tilde{\Omega}\left(n^2/\beta^2\right)$ two-party communication lower bound [Halld\'orsson 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/\beta\right)$ bits of space, leaving a (deterministic) gap of size $\tilde{O}(\beta)$. We resolve this deterministic gap with an (almost) tight lower bound: any deterministic algorithm for either problem must use $\Omega\left(\frac{n^2}{\beta\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.

1 Introduction

The paper asks whether the deterministic gap in streaming approximation for Maximum Clique and Maximum Independent Set can be closed. It answers with a strong lower bound and identifies the power of randomness for both problems.

1 Introduction

  • The streaming model presents edges one at a time in arbitrary order and requires a valid output for the final surviving edges.The algorithm receives the vertex set in advance, outputs only at stream end, and is evaluated by space rather than computation time.Source: §1 · p. 2
  • Earlier randomized work gave a one-pass insertion-deletion algorithm and a matching insertion-only lower bound, both of size ˜O(n^2/β^2) and ˜Ω(n^2/β^2), respectively [HSSW12].The cited bounds apply to both Maximum Clique and Maximum Independent Set and are tight up to polylogarithmic factors.Source: §1 · p. 2

1.1 Our Contributions

  • The work resolves the deterministic-gap question with a strong lower bound, making the power of randomisation explicit for both problems.The authors relate this to the previously understood case of combinatorial independent sets [Ye25].Source: §1.1 · p. 3

1.2 Related Work

  • For deterministic lower bounds, adaptively choosing Alice's and Bob's inputs avoids relying on a fixed input distribution to obtain only a randomized lower bound [ACS22] [Ye25].The authors take inspiration from this adaptive setup but use a different compression argument and combinatorial construction.Source: §1.2 · p. 3

1.3 Our Techniques

  • The graph construction uses Θ(n^2/β^2) gadgets, each requiring Ω(1) communication bits, and keeps the same packing while replacing each with one requiring Ω(β) bits deterministically.Source: §1.3 · p. 4
  • In a single gadget, Alice's message determines a common core; Bob chooses a compatible vertex subset and supplies edges outside that core, leaving uncertainty about whether a large clique exists.This preserves a positive probability of a large clique while limiting what Bob can safely output.Source: §1.3 · p. 4
  • The analysis relates communication cost to the common-core size and the distribution of the combined graph, using information-theoretic counting.For the full construction, the authors combine Θ(n^2/β^2) gadgets scaled to at most 18·β vertices each.Source: §1.3 · p. 5

1.4 Outline of this Work

  • The proof presents the Maximum Clique lower bound, adapts it to Maximum Independent Set, and places the folklore derandomised algorithm in an appendix.The outline identifies the single-gadget proof before the combination of multiple gadgets.Source: §1.4 · p. 5

2 Preliminaries

The preliminaries set the random-graph conventions and notation, define the one-way communication framework used for streaming lower bounds, and introduce information-theoretic quantities for the compression arguments.

2 Preliminaries

  • For G distributed as G_n,1/2, each edge is independently realized with probability 1/2, and its clique number is at most 3 log n with probability at least 1 − 1/n.Logarithms are base two; G denotes the edge-complement, and G[U] the subgraph induced by U.Source: §2 · p. 5
  • Figure 1 illustrates producing a gadget for the Maximum Clique lower bound, with hatching marking edges partially filled according to the sampled base graph.The figure distinguishes Alice’s sampled-subset graph from Bob’s message-ambiguous view and marks their common core.Source: Figure 1 · p. 6, §2 · p. 6

2.1 Communication Complexity

  • In one-way communication, Alice sends Bob a message about her edge input, and Bob outputs for the shared graph; communication lower bounds imply one-pass streaming space lower bounds.The protocol’s cost is its largest message size over inputs.Source: §2.1 · p. 7

2.2 Counting with Information Theory

  • The section defines message-wise mutual information as J(X | Y = y) = H(X) − H(X | Y = y) and identifies I(EA; M) as a protocol’s information cost.Information cost lower-bounds communication cost.Source: §2.2 · pp. 7–8

3 Theorem 1.1: Maximum Clique

Section 3 begins the proof of a lower bound for approximate Maximum Clique.

3 Theorem 1.1: Maximum Clique

  • Theorem 1.1 states a condition on one-pass deterministic streaming algorithms for approximate Maximum Clique.The supplied theorem passage does not include the condition’s bound.Source: §3 · p. 9

3.1 Step One: A Single Gadget

The single-gadget argument builds a hard one-way communication game for Maximum Clique, then uses message compression to constrain Bob’s output. It yields a deterministic communication lower bound and a β-dependent corollary.

3.1.1 The Hard Communication Game

  • The game samples GBase from Gn,1/2 and gives Alice induced edges on a subset A; Bob’s input is constructed after receiving Alice’s message.Source: §3.1.1 · pp. 9–10
  • The constructed graph G is a simple graph, and therefore a valid input graph.Source: §3.1.1 · p. 10

3.1.2 Understanding |VCommon| (the Compression Step)

  • If J(A | M = m) = o(n) bits, then the common core VCommon has size o(n).Source: §3.1.2 · p. 11

3.1.4 Understanding Bob’s Output

  • With probability at least 1 − 2/n over GBase, Bob’s output has size at most 3 log n.Source: §3.1.4 · p. 13

3.1.5 Bringing it all Together

  • The argument obtains an input with ω(G) ≥ n/4 while Bob’s output is at most 3 log n.Source: §3.1.5 · p. 14
  • For β < n/12, any deterministic protocol computing a better-than (β/log n)-approximate Maximum Clique must send a message of size Ω(β).Source: §3.1.5 · p. 15

3.2 Step Two: Combining Multiple Gadgets

The multi-gadget construction packs separate instances into one graph and extends the compression argument to control Bob’s output. The combined instance retains a large clique while Bob’s output remains small.

3.2.1 Packing Edge-Disjoint Cliques into G

  • Each packed vertex subset Bi contains an independent instance of size 18 · β.Source: §3.2.1 · p. 15

3.2.3 The Multi-Gadget Compression Step

  • The multi-gadget argument adapts the single-gadget compression analysis to Amin and VCommon|min; message sizes o(n^2/β) are the threshold considered.Source: §3.2.3 · p. 16
  • If J(Amin | M = m) = o(β), then |VCommon|min| = o(β).Source: §3.2.3 · p. 17

3.2.4 Understanding ω(G)

  • When Amin is the selected subset and |VCommon|min| = o(β), the constructed graph has ω(G) ≥ 8 · β for sufficiently large n.Source: §3.2.4 · p. 17

3.2.5 Understanding Bob’s Output

  • With probability at least 1 − 2/n over GBase, Bob’s output has size at most 6 · log n.Source: §3.2.5 · p. 17

3.2.6 Bringing it all Together

  • The combined instance has ω(G) ≥ 8 · β while |OUT| ≤ 6 · log n.Source: §3.2.6 · p. 19

4 Theorem 1.2: The Extension to Maximum Independent Set

The section adapts the deterministic communication lower-bound proof for approximate Maximum Clique to Maximum Independent Set. It changes the hard input construction to preserve a simple graph, analyzes the resulting independent sets, and combines these results with the earlier compression arguments to prove Theorem 1.2.

4.1 The Hard Communication Game

  • The construction removes the edges previously assigned to Alice and Bob so the input remains a simple graph and the earlier cliques correspond to independent sets.Simply complementing the earlier inputs would not ensure that Alice’s and Bob’s edge sets were disjoint.Source: §4.1 · p. 20

4.2 Understanding α(G)

  • Amin \ VCommon|min forms an independent set in both EA and EB, giving α(G) ≥ 9 · β − |VCommon|min|.The displayed bound follows because that same set is independent in the combined graph G.Source: §4.2 · p. 21
  • Bob’s output has size at most 3 · log n with probability at least 1 − 1/n over GBase.To include a non-edge, Bob must know its status in both EA and EB; the certain non-edges lie within the sets VCommon|i.Source: §4.2 · p. 21

4.3 Bringing it all Together

  • Theorem 1.2 follows by combining Lemmas 4.1 and 4.2 with the compression arguments from Section 3.2.3 and Lemma 3.8.The section presents the new input distribution and independent-set analyses, while leaving the compression arguments unchanged.Source: §4 · p. 20, §4.3 · p. 21

AI Declaration

The authors report using AI tools for spelling and grammar assistance and for fixing a minor error in an earlier version of Claims 8 and 9.

AI Declaration

  • AI tools assisted with spelling and grammar and helped fix a minor error in an earlier version of Claims 8 and 9.The authors state that all other mathematical work was done without AI tools.Source: AI Declaration · p. 22

A The Algorithm

The appendix gives a folklore deterministic algorithm for approximate Maximum Clique or Maximum Independent Set. It partitions the vertices, stores each part’s induced graph during the stream, and returns the largest optimal solution found within a part.

A The Algorithm

  • The algorithm partitions V into at most β parts, stores their induced edges and deletions, then returns the largest optimal solution found within a part.The appendix presents the derandomization for completeness and claims no novelty.Source: A The Algorithm · p. 24
  • Averaging ensures some part contains at least a 1/β fraction of the vertices in an optimal solution, yielding a sufficiently large induced solution.The algorithm computes an optimal solution within each part and returns the largest.Source: A The Algorithm · p. 24
  • The algorithm uses O(n^2/β) bits when β < n/log n and O(n · log(n)) bits otherwise.These bounds are stated for maintaining the adjacency matrices during the stream.Source: A The Algorithm · p. 24
Loading 2609.18635v1…