Re: Time complexity of couting the number of cliques on k nodes

On Aug 16, 2:45 pm, jamesblacksm...@xxxxxxxxx wrote:
Hi,

does anyone know what is currently
known about the complexity of counting
the number of complete subgraphs with
a fixed number of vertices in an undirected
simple graph? I am particularly interested in
the case that the number of vertices of the
clique is not part of the input, merely the number
of vertices of the host graph is part of the input.
What algorithms are known for this today and what
is their performance? Do you know useful surveys?

Thank you,
James

Unfortunately, I do not know the literature. However, if you find
one
reference that mentions the problem, you can often use a citation
index
to find later work on the same problem. Often one forgets about using
the citation index to find recent literature.

The following psuedocode is a start ( in my humble opinion ) on
solving
the problem efficiently, especially as the clique size k gets
larger.
I assume an undirected loopless graph for input, k the clique size is
hardcoded into the program, and I leave many implementation details
and
bug-finding to the reader.

1. Sort the vertices by (remaining) degree.
2. Remove all vertices of degree less than k-1 and their neighboring
edges
from (a copy of) the graph
3. If anything was removed, take the resulting subgraph and go to step
1.
4. Using a vertex v of smallest degree:
4 a. find the set of adjacent neighbors N(v).
4 b. For each (k-1)-sized subset S of N(v), if S is a k-1 clique,
print v, S
4 c. Remove v and its neighboring edges from the graph.
5. If at least k vertices remain, go to step 1.
6. Stop.

The hope here is that successive removal of vertices reduces the
amount
of work needed. This removal and sorting is at most O(V*V*log(V)+E),
where V is the number of vertices in the input graph and E the number
of edges in the input graph. Step 4b hides the work: It will take
(d(v) choose (k-1)) iterations of some subroutine that helps find a
clique,
where d(v) is the degree of the vertex in the subgraph being
considered at
that time. Running this algorithm on a clique of size (k+m) should
give
an output of (k+m choose k) cliques.

There are ways to speed up 4b. For example, if an non-edge (u,w) is
encountered, one can skip a number of subsets which contain (u,w).
I recommend sorting N(v) by something which reveals the non-edges
early,
so that a lexicographic ordering of the (N(v) choose (k-1)) subsets
does a
lot of initial skipping. In any case, there is a potential for an
exponential-sized number of k-cliques, so only rough bounds can be
given
without knowing anything further about the graph.

One also does not need step 1 if one has a way of finding the vertex
of
smallest degree quickly in a subgraph. Similarly, steps 1-3 are just
forms of preprocessing. If one does not mind the extra work of
looking
for (k-1) subsets in a set strictly smaller than (k-1) elements, just
iterating step 4 enough times will also do the job. You can even try
to use 4 recursively, calling a different version of step 4 to use
during 4b.

If you know of anything that is substantially different from this,
and still effectivein solving the problem, I would appreciate your
posting a reference here in this thread.

Gerhard Paseman, 2008.08.16
.

Relevant Pages