Conference rusure::math

>A "local maximal clique" in a graph is a subgraph which is:
> [1] complete (every vertex is connected to any other vertex)
> [2] not included in any larger complete subgraph.
>
>Given a (undirected) graph, what is a good algorithm to locate all the local
>maximal cliques?  

For every node Nk in the graph
    if Nk is in a clique Cn
        add all the arcs at Nk to Cn
    else
	start a new clique Cj
	for every arc at Nk
	    Add the arc to Cj
	    Let Ni be the node at the other end of the arc
	    if Ni is in a clique Cn, merge Cj, Cn into Cn
	    else add Ni to Cj

The cost of this algorithm is the number of nodes * the cost of determining 
whether a node is in an average clique, plus the cost of checking the arcs, 
which I assume is negligible because of the sparseness.

Re .1:

Consider the graph which looks like two triangles joined along a common
base.  It has 4 vertices and 5 edges:

G(V, E) = ({1,2,3,4}, {{1,2}, {1,3}, {2,3}, {2,4}, {3,4}})

There are two LCM's in this graph - each one is one of the triangles (K(3)):

G1 = ({1,2,3}, {{1,2}, {2,3}, {1,3}})
	-and-
G2 = ({2,3,4}, {{2,3}, {3,4}, {2,4}})

If I apply your algorithm, I get one "clique" (which isn't even a graph,
because it contains 4 "unterminated" edges).  It consists of the two
vertices common to both triangles, plus all the edges:

C1 = ({2,3}, {{1,2}, {2,3}, {3,4}, {1,3}, {2,4}})


Have I executed your algorithm incorrectly, or is there a bug in it?
I don't have my copy of Harary handy.

(Off hand, I think the fact that your algorithm merges cliques without
determining that the union forms a complete subgraph is a mistake. 
And I think there is a step missing which adds a node to a clique).

However, since there are as many as 2**n complete subgraphs of a graph
with n vertices (right?), I think this problem is rather expensive to solve
in general.  I admit that I'm not sure where the assumption that the graph
is sparse comes into your algorithm in a manner which makes it cheap to
execute in such cases, though.
				/AHM/THX

I confess I'm not certain I understand the definition of 'clique'.

(.0)
>A "local maximal clique" in a graph is a subgraph which is:
> [1] complete (every vertex is connected to any other vertex)
> [2] not included in any larger complete subgraph.
..........................******....................
What does larger mean?

(.1)
>For every node Nk in the graph
>    if Nk is in a clique Cn
>        add all the arcs at Nk to Cn
>    else
	start a new clique Cj *composed of Nk and its arcs*
	......................*****************************

.0 specified, I believe, that the graphs of interest are sparse.

Re .3:

I'm don't recall whether "clique" has a single accepted definition in
general.  However, this problem statement seems to define it in terms of
"subgraph", "complete" and "maximal". I assume you know what a complete
graph is.  I figure "larger" means "has more vertices" or "has more edges".
Since a complete graph with n vertices has n(n-1)/2 edges, they are both
the same thing for the purposes of this problem.

In the past, I was not familiar with a quantitative definition of "sparse"
for graphs.  However, the book "Algorithms" by Robert Sedgewick defines
a sparse graph as one which has no more than n log(2) n edges, where
n is the number of vertices.  Apparently this definition is the break-even
point for a number of important graph algorithms in deciding whether
to use an adjacency matrix or adjacency list representation.
				/AHM/THX

The way the problem of finding the maximal clique is often solved is by
successively finding all the 1-cliques, 2-cliques, 3-cliques, and so on.

The 1-cliques are simply all the individual nodes.  The 2-cliques are
the pairs of nodes that are connected by an edge (actually, it also
includes the connecting edge, but we'll allow some imprecision on this
part of the definition).

The (n+1)-cliques can be found by attempting to add another node to each of
the n-cliques; the added node must share an edge with each of the n nodes
in the n-clique.

Since an (n+1)-clique contains n+1 n-cliques, we might try to combine
n-cliques, instead of adding nodes; this is useful when there are many
nodes, but only a few n-cliques.  That is, rather than trying to add
each of the nodes (from the original graph), only try to add nodes that
were part of some (other) n-clique.

An interesting question is:

	What is the maximum number of maximal cliques that may be
	in an graph of n nodes?

>	What is the maximum number of maximal cliques that may be
>	in an graph of n nodes?

If there are no arcs, there are N maximal cliques. Can there be more?

    Re .7:
    
    Consider A connected to B and B connected to C.  {A, B} and the edge
    connecting them is a maximal clique, as is {B, C}. 
    
    For a more general example, consider a clique with n nodes and the
    requisite n(n-1)/2 edges.  If you remove all edges between each two
    nodes of a set of r nodes, the remaining graph has maximal cliques for
    every set of n+1-r nodes which includes exactly one of the r nodes.
    Obviously there are r such cliques. 
    
    To go on, remove all edges between each two nodes of a set of s nodes
    disjoint from the set of r nodes.  The remaining graph has maximal
    cliques for every set of n+1-r+1-s nodes which includes exactly one of
    the r nodes and exactly one of the s nodes.  There are rs such cliques.
    
    To get specific again, consider the nodes {A, B, C, D, E, F} with the
    edges {AD, AE, AF, BD, BE, BF, CD, CE, CF}.  This is the complete graph
    on {A, B, C, D, E, F} with edges between all pairs of {A, B, C} and {D,
    E, F} removed.  Maximal cliques for it are {A, D}, {A, E}, {A, F}, and
    so on, for nine cliques. 
    
    If such removals are the way to achieve the maximum number of maximal
    cliques, then this problem has been discussed already in this
    conference in the guise of asking how to find numbers which sum to N
    with the largest product. 
    
    
    				-- edp 

    That doesn't seem to maximize it.  In your example of 6 nodes,
    you had 9 maximal cliques.  Here's an example with 12:

			A---B
			|\  |
			| E |	F (F connects to each of A,B,C,D, and E,)
			|  \|	  (but I've elected to not draw the arcs)
			D---C

    Maximal cliques: { AB, AD, AE, BC, CD, CE, FAB, FAD, FAE, FBC, FCD, FCE }.

Re .9:

AB can't be a maximal clique in that graph, because AB is a subgraph of
FAB, and you claimed that was maximal, too.  The same problem removes AD,
AE, BC, CD and CE from consideration.  This leaves you with a graph
that has 6 vertices and 6 alleged maximal cliques.
				/AHM

    Merci for the correction.

re .7
    Yeesh!  That's an exponential number of maximal cliques!
    Nitsan, do you really want *all* of them?

The problem was not originally mine, so I passed the info to the original
person. Thanx!

Nitsan