Premium
Finding cliques using few probes
Author(s) -
Feige Uriel,
Gamarnik David,
Neeman Joe,
Rácz Miklós Z.,
Tetali Prasad
Publication year - 2020
Publication title -
random structures and algorithms
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 1.314
H-Index - 69
eISSN - 1098-2418
pISSN - 1042-9832
DOI - 10.1002/rsa.20896
Subject(s) - adjacency matrix , combinatorics , clique graph , vertex (graph theory) , clique , mathematics , computation , graph , simplex graph , random graph , discrete mathematics , adjacency list , algorithm , line graph , graph power
Consider algorithms with unbounded computation time that probe the entries of the adjacency matrix of an n vertex graph, and need to output a clique. We show that if the input graph is drawn at random fromG n , 1 2(and hence is likely to have a clique of size roughly 2 log n ), then for every δ <2 and constant ℓ , there is an α <2 (that may depend on δ and ℓ ) such that no algorithm that makes n δ probes in ℓ rounds is likely (over the choice of the random graph) to output a clique of size larger than α log n .