TY - GEN

T1 - Streaming and communication complexity of clique approximation

AU - Halldórsson, Magnús M.

AU - Sun, Xiaoming

AU - Szegedy, Mario

AU - Wang, Chengu

PY - 2012

Y1 - 2012

N2 - 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.

AB - 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.

UR - http://www.scopus.com/inward/record.url?scp=84883771760&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=84883771760&partnerID=8YFLogxK

U2 - 10.1007/978-3-642-31594-7_38

DO - 10.1007/978-3-642-31594-7_38

M3 - Conference contribution

AN - SCOPUS:84883771760

SN - 9783642315930

T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

SP - 449

EP - 460

BT - Automata, Languages, and Programming - 39th International Colloquium, ICALP 2012, Proceedings

T2 - 39th International Colloquium on Automata, Languages, and Programming, ICALP 2012

Y2 - 9 July 2012 through 13 July 2012

ER -