<p>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.</p>

<p>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.</p>

<p>Maybe there are some heuristics.</p>

CC BY-SA 3.0
2014-08-22T16:59:49.563Z
2014-08-22T16:59:49.563Z
Saeed
<p>here are two refs with some analysis of this problem and the first shows/ measures performance improvements over batch algorithms.</p>
<ul>
<li><p><a href="https://link.springer.com/article/10.1007/s10462-011-9250-x" rel="nofollow noreferrer">Incremental K-clique clustering in dynamic social networks</a> Duan, Li, Lu</p>
<blockquote>
<p>Based on the change stream model, the incremental version of a well known k-clique clustering problem is studied and incremental k-clique clustering algorithms are proposed based on local DFS (depth first search) forest updating technique. It is theoretically proved that the proposed algorithms outperform corresponding static ones and incremental spectral clustering algorithm in terms of time complexity. ... Experimental results show that incremental k-clique clustering algorithms are much more efficient than corresponding static ones, and have no accumulating errors that incremental spectral clustering algorithm has and can capture the evolving details of the clusters that snapshot graph model based algorithms miss.</p>
</blockquote>
</li>
<li><p><a href="https://ieeexplore.ieee.org/document/5370363" rel="nofollow noreferrer">A Realtime Clique Detection Algorithm: Time-Based Incremental Label Propagation</a> Pang, Chen, Wei</p>
</li>
</ul>

CC BY-SA 4.0
2014-08-22T15:44:40.750Z
2022-07-03T06:33:17.780Z
2022-07-03T06:33:17.780Z
vzn
<p>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?</p>

CC BY-SA 3.0
2014-08-21T19:25:09.713Z
@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.
gornikm
<graph-theory><graph-algorithms><clique>
Algorithms for online clique detection
gornikm
# Algorithms for online clique detection

(Asked by: username_0 on 2014-08-21)

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?

**Tags:** graph-theory, graph-algorithms, clique

> **Comments:**
> **username_0**: @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.  

---

## 2 answers

### Answer by username_1 on 2014-08-22. Score: 6 | Accepted answer

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.

Maybe there are some heuristics.


---

### Answer by username_2 on 2014-08-22. Score: 1

here are two refs with some analysis of this problem and the first shows/ measures performance improvements over batch algorithms.

* [Incremental K-clique clustering in dynamic social networks](https://link.springer.com/article/10.1007/s10462-011-9250-x) Duan, Li, Lu

  > Based on the change stream model, the incremental version of a well known k-clique clustering problem is studied and incremental k-clique clustering algorithms are proposed based on local DFS (depth first search) forest updating technique. It is theoretically proved that the proposed algorithms outperform corresponding static ones and incremental spectral clustering algorithm in terms of time complexity. ... Experimental results show that incremental k-clique clustering algorithms are much more efficient than corresponding static ones, and have no accumulating errors that incremental spectral clustering algorithm has and can capture the evolving details of the clusters that snapshot graph model based algorithms miss.
* [A Realtime Clique Detection Algorithm: Time-Based Incremental Label Propagation](https://ieeexplore.ieee.org/document/5370363) Pang, Chen, Wei


---

