Clique problem, cutting plane proofs and communication complexity
From MaRDI portal
Publication:456115
DOI10.1016/J.IPL.2012.07.003zbMATH Open1248.68248arXiv1203.5414OpenAlexW2036953534MaRDI QIDQ456115FDOQ456115
Authors: Stasys Jukna 
Publication date: 23 October 2012
Published in: Information Processing Letters (Search for Journal in Brave)
Abstract: Motivated by its relation to the length of cutting plane proofs for the Maximum Biclique problem, 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.
Full work available at URL: https://arxiv.org/abs/1203.5414
Recommendations
- Some improved bounds on communication complexity via new decomposition of cliques
- A simple lower bound for monotone clique using a communication game
- Randomized communication versus partition number
- Ordered biclique partitions and communication complexity problems
- Deterministic communication vs. partition number
Analysis of algorithms and problem complexity (68Q25) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69)
Cites Work
- Monotone Circuits for Connectivity Require Super-Logarithmic Depth
- On cliques in graphs
- Boolean function complexity. Advances and frontiers.
- The monotone circuit complexity of Boolean functions
- Title not available (Why is that?)
- Sorting in \(c \log n\) parallel steps
- Short monotone formulae for the majority function
- The maximum edge biclique problem is NP-complete
- On graphs with polynomially solvable maximum-weight clique problem
- Title not available (Why is that?)
- Parameterized complexity of DPLL search procedures
- On cutting-plane proofs in combinatorial optimization
- Title not available (Why is that?)
- A simple lower bound for monotone clique using a communication game
- Monotone circuits for matching require linear depth
- An upper bound for the number of maximal independent sets in a graph
Cited In (3)
This page was built for publication: Clique problem, cutting plane proofs and communication complexity
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q456115)
