Incrementally Maintaining the Number of l-cliques
Fabrizio Grandoni · OpenGrey (Institut de l'Information Scientifique et Technique) · 2002
The main contribution of this paper is an incremental algorithm to update the number of $l$-cliques, for $l \\geq 3$, in which each node of a graph is contained, after the deletion of an arbitrary node. The initialization cost is $O(n^{\\omega p+q})$, where $n$ is the number of nodes, $p=\\lfloor \\frac{l}{3} \\rfloor$, $q=l \\pmod{3}$, and $\\omega=\\omega(1,1,1)$ is the exponent of the multiplication of two $n x n$ matrices. The amortized updating cost is $O(n^{q}T(n,p,\\epsilon))$ for any $\\epsilon \\in [0,1]$, where $T(n,p,\\epsilon)=\\min\\{n^{p-1}(n^{p(1+\\epsilon)}+n^{p(\\omega(1,\\epsilon,1)-\\epsilon)}),n^{p \\omega(1,\\frac{p-1}{p},1)}\\}$ and $\\omega(1,r,1)$ is the exponent of the multiplication of an $n x n^{r}$ matrix by an $n^{r} x n$ matrix. The current best bounds on $\\omega(1,r,1)$ imply an $O(n^{2.376p+q})$ initialization cost, an $O(n^{2.575p+q-1})$ updating cost for $3 \\leq l \\leq 8$, and an $O(n^{2.376p+q-0.532})$ updating cost for $l \\geq 9$. An interesting application to constraint programming is also considered.