Given an arbitrary undirected graph $G$ with $n$ vertices, I am interested in counting the number of cliques. (For example, the number of cliques of a complete graph $K_n$ is trivially $2^n-1$;the number of cliques of a tree $T_n$ is $2n-1$.) I think it is a challenging task when $n$ is large. So I need a good upper/lower bound estimation method. Thanks in advance!
$\begingroup$
$\endgroup$
3
-
1$\begingroup$ Are you looking for an algorithm? I guess for LB you can exhaustively count cliques or size $r = O(1)$ and for UB argue that one edge missing "destroys" $n \choose 2$ cliques. $\endgroup$– QiseCommented Jun 29, 2023 at 9:27
-
$\begingroup$ Yes, I am looking for practical algorithms or formulas. $\endgroup$– user1116616Commented Jun 29, 2023 at 9:59
-
$\begingroup$ related: cs.stackexchange.com/questions/9209 $\endgroup$– user1116616Commented Jul 3, 2023 at 8:56
Add a comment
|
1 Answer
$\begingroup$
$\endgroup$
The tree and the complete graph are the best possible lower and upper bound for a completely arbitrary graph. If you want better bounds you have to provide some more information about the graph.
Otherwise it should be possible to compute or at least estimate an average numbers of cliques for a graph on $n$ vertices. There are only finitely many graphs for any given $n$, so in principle the entire distribution of cliques can be computed.
As the dumb trivial example: there are only 2 distinct graphs with $2$ vertices, either there is an edge or there isn't. Hence an arbitrary graph on $2$ vertices has a $50\%$ chance of having 2 cliques and a $50\%$ chance of having 3 cliques.
