Finding cliques using few probes | Zendy

Feige Uriel | Zendy; Gamarnik David | Zendy; Neeman Joe | Zendy; Rácz Miklós Z. | Zendy; Tetali Prasad | Zendy

AI Assistant Blog Pricing

Home ZAIA Blog

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 .

This content is not available in your region!

Continue researching here.

Having issues? You can contact us here

Accelerating Research