Clique problem, cutting plane proofs and communication complexity

DOI10.1016/J.IPL.2012.07.003MaRDI QIDQ456115zbMATH OpenOpenAlexFDO

Authors Stasys Jukna

Publication date 23 October 2012

Published in Information Processing Letters (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1203.5414

zbMATH Keywords

computational complexitycommunication complexityclique problemcutting plane proof

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69)

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.

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

Cites work

• scientific article; zbMATH DE number 4008289 (Why is no real title available?)
• scientific article; zbMATH DE number 861332 (Why is no real title available?)
• scientific article; zbMATH DE number 1445296 (Why is no real title available?)
• A simple lower bound for monotone clique using a communication game
• An upper bound for the number of maximal independent sets in a graph
• Boolean function complexity. Advances and frontiers.
• Monotone Circuits for Connectivity Require Super-Logarithmic Depth
• Monotone circuits for matching require linear depth
• On cliques in graphs
• On cutting-plane proofs in combinatorial optimization
• On graphs with polynomially solvable maximum-weight clique problem
• Parameterized complexity of DPLL search procedures
• Short monotone formulae for the majority function
• Sorting in \(c \log n\) parallel steps
• The maximum edge biclique problem is NP-complete
• The monotone circuit complexity of Boolean functions

Cited in

(3)

• Ordered biclique partitions and communication complexity problems
• Some improved bounds on communication complexity via new decomposition of cliques
• Interactive proofs and the hardness of approximating cliques

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)