# Algorithms for online clique detection

Are there any algorithms which let you detect cliques when adding/deleting edges based on previously detected cliques? What would be the time/memory complexity of this approach?

• @RB Yes, I was wondering if it is possible to avoid checking the whole graph with each update (at the expense of memory needed for storing existing cliques) by inspecting only cliques existing in the neighborhood of the added edge, e.g. joining cliques when edge is added, dividing when edge is removed. Aug 21, 2014 at 19:25

First of all I think you mean a maximum clique, not all cliques (and even not maximal cliques). As otherwise e.g in $K_n$ there are $2^n−1$ cliques.
If the question is the one that I said, then there is no polynomial time online algorithm for update (unless P=NP). If there is such an algorithm $A$, given a graph $G$, we can find a maximum clique of $G$ in polynomial time. Just start from a graph on $n$ vertex without any edge and add edges of $G$ one by one and update information in each step by $A$. After adding all edges we have a maximum clique. Note that if we use exponential memory at some steps we can do this, but to write on exponential memory we need exponential time as well.