# Online algorithm for finding of clique of size k

I am trying to write an online algorithm that can detect cliques of size k. I first start out with a set of vertices. For each iteration, I add an edge. The algorithm will detect the first time an edge would create a clique of size k. What is an efficient algorithm that can complete this task, and what is the time complexity?

• Given that the offline problem is NP-hard (for non-constant $k$), I'm not sure what you can expect... – Yuval Filmus Jun 22 at 0:08

This problem is not going to have a very efficient solution. Looking at the $$k=3$$ case should be good start. In this case one can solve this problem with $$O(|E|)$$ space by keeping an (online) adjacency set for each vertex and when an edge $$(u,v)$$ arrives comparing the adjacency sets of vertices $$u$$ and $$v$$ for a collision (in time linear in the size of the smaller set) and then adding $$(u,v)$$ to the sets of vertex $$u$$ and $$v$$.
The run time of this algorithm would be $$\sum_v d(v)^2$$, where $$d(v)$$ is the degree of vertex $$v$$ in the final graph. This is never bigger than $$O(n^3)$$, where $$n$$ is the number of vertices in the final graph.
It is unknown whether triangle detection (i.e., a clique of size 3) can be done in less than $$n^3$$ time even if you had the entire graph before you. See this, for instance.