Streaming and communication complexity of clique approximation

Magnús M. Halldórsson, Xiaoming Sun, Mario Szegedy, Chengu Wang

Research output: Chapter in Book/Report/Conference proceedingConference contribution

9 Scopus citations

Abstract

We consider the classic clique (or, equivalently, the independent set) problem in two settings. In the streaming model, edges are given one by one in an adversarial order, and the algorithm aims to output a good approximation under space restrictions. In the communication complexity setting, two players, each holds a graph on n vertices, and they wish to use a limited amount of communication to distinguish between the cases when the union of the two graphs has a low or a high clique number. The settings are related in that the communication complexity gives a lower bound on the space complexity of streaming algorithms. We give several results that illustrate different tradeoffs between clique separability and the required communication/space complexity under randomization. The main result is a lower bound of Ω(n2/r2log2n)-space for any r-approximate randomized streaming algorithm for maximum clique. A simple random sampling argument shows that this is tight up to a logarithmic factor. For the case when r = o(logn), we present another lower bound of Ω(n2/r 4. In particular, it implies that any constant approximation randomized streaming algorithm requires Ω(n2) space, even if the algorithm runs in exponential time. Finally, we give a third lower bound that holds for the extremal case of s - 1 vs. R(s) - 1, where R(s) is the s-th Ramsey number. This is the extremal setting of clique numbers that can be separated. The proofs involve some novel combinatorial structures and sophisticated combinatorial constructions.

Original languageEnglish (US)
Title of host publicationAutomata, Languages, and Programming - 39th International Colloquium, ICALP 2012, Proceedings
Pages449-460
Number of pages12
EditionPART 1
DOIs
StatePublished - 2012
Event39th International Colloquium on Automata, Languages, and Programming, ICALP 2012 - Warwick, United Kingdom
Duration: Jul 9 2012Jul 13 2012

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
NumberPART 1
Volume7391 LNCS
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349

Other

Other39th International Colloquium on Automata, Languages, and Programming, ICALP 2012
Country/TerritoryUnited Kingdom
CityWarwick
Period7/9/127/13/12

All Science Journal Classification (ASJC) codes

  • Theoretical Computer Science
  • Computer Science(all)

Fingerprint

Dive into the research topics of 'Streaming and communication complexity of clique approximation'. Together they form a unique fingerprint.

Cite this