Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > DETAIL:

Paper:

TR12-039 | 17th April 2012 13:01

Clique Problem, Cutting Plane Proofs, and Communication Complexity

RSS-Feed




TR12-039
Authors: Stasys Jukna
Publication: 17th April 2012 13:01
Downloads: 1299
Keywords: 


Abstract:

Motivated by its relation to the length of cutting plane proofs for the Maximum Biclique problem, here we consider the following communication game on a given graph G, known to both players. Let K be the maximal number of vertices in a complete bipartite subgraph of G (which is not necessarily an induced subgraph if G is not bipartite). Alice gets a set A of vertices, and Bob gets a disjoint set B of vertices such that |A|+|B|>K. The goal is to find a nonedge of G between A and B. We show that O(\log n) bits of communication are enough for every n-vertex graph.



ISSN 1433-8092 | Imprint