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
-
1$\begingroup$ Given that the offline problem is NP-hard (for non-constant $k$), I'm not sure what you can expect... $\endgroup$– Yuval FilmusCommented Jun 22, 2019 at 0:08
Add a comment
|
1 Answer
$\begingroup$
$\endgroup$
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.
