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?

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

Since I don't have enough points for a comment:

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.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.