Finding cliques and dense subgraphs using edge queries

Endre Csóka, András Pongrácz

We consider the problem of finding a large clique in an Erdős--Rényi random graph where we are allowed unbounded computational time but can only query a limited number of edges. Re…