Maximalizing cliques

A set in a collection of sets is maximal if it is not a subset of any other set in the collection.

A clique is a complete subgraph of a graph - one in which every pair of nodes that participate in the subgraph are connected by an edge.

A clique in a collection of cliques is maximal if it is not a subgraph of any other clique in the collection.

I'll usually identify a clique by the set of nodes that participate in the clique - I'll often refer to the set of node labels as a 'clique' - a convenient if inaccurate shorthand.

Suppose that we have somehow obtained a clique of a graph and wish to make it large - as large as we can, in fact.

I call the process of taking a clique and making it as large as you can contrive the maximalization of the clique - you are, in fact, constructing a maximal clique of the graph from the original clique.

In one sense, this is simplicity itself, for you simply need to repeatedly pick a node that is not in the clique and add it to the new clique if and only if it has an edge with every node that is already in the clique, stopping once all nodes that are not in the resulting clique have been tested and rejected.

Here's the issue: with every choice of a node to add, you may be precluding the later choice of other nodes - you can't have your cake and eat it, too.

You might be tempted to think of this process as a branching tree, in which the original clique is the root of the tree, and each branch represents the choice of a node to add to the clique. This isn't generally the case, however - because it is possible for different sequences of adding nodes to converge. The data structure that we're actually working with is a directed acyclic graph, however tree-like it may often appear.

What's the big question? What algorithm, heuristic or otherwise, should we use to try to construct the largest maximal clique that we can tease out of the graph?

Following is a very simple algorithm for maximalizing a clique. Simple because it tries to add nodes to the clique in ascending node-label order.

I think that it can be greatly improved upon.

Algorithm for maximalizing a clique

void
MaximalizeClique( IN   Set &     clique,
                  IN   Graph &   graph,
                  OUT  Set &     maximalizedClique )
{
    maximalizedClique = clique;

    Set   nonParticipants  =  graph.Nodes;

    nonParticipants.DifferenceWith( clique );

    foreach ( int node in nonParticipants )
    {
        if ( graph.AugmentedAdjacencySet[node].Contains( maximalizedClique ) )
        {
            maximalizedClique.AddElement( node );
            nonParticipants.RemoveElement( node );
        }
    }
}

Example of the maximalization of a clique

Augmented Adjacency Sets for Graph

0 : { 0, 1, 2, 3, 6, 7, 10, 11, 13, 14 }
1 : { 0, 1, 3, 7, 9, 10, 12, 14 }
2 : { 0, 2, 3, 5, 6, 10, 11 }
3 : { 0, 1, 2, 3, 5, 6, 7, 10, 12, 13, 14 }
4 : { 4, 5, 7, 8, 9, 10, 13 }
5 : { 2, 3, 4, 5, 6, 7, 9, 10, 11, 13 }
6 : { 0, 2, 3, 5, 6, 7, 8, 12, 13, 14 }
7 : { 0, 1, 3, 4, 5, 6, 7, 10, 11, 12, 13, 14 }
8 : { 4, 6, 8, 11, 12, 13, 14 }
9 : { 1, 4, 5, 9, 14 }
10 : { 0, 1, 2, 3, 4, 5, 7, 10, 12, 13, 14 }
11 : { 0, 2, 5, 7, 8, 11, 13 }
12 : { 1, 3, 6, 7, 8, 10, 12 }
13 : { 0, 3, 4, 5, 6, 7, 8, 10, 11, 13 }
14 : { 0, 1, 3, 6, 7, 8, 9, 10, 14 }


Let's start with the clique { 0, 3, 7 }

I'll apply the algorithm presented above to this clique:

node    AAS contains maximalClique?    resulting maximalClique

initially                               { 0, 3, 7 }

  1                 yes                 { 0, 1, 3, 7 }
  2                 no                  { 0, 1, 3, 7 }
  4                 no                  { 0, 1, 3, 7 }
  5                 no                  { 0, 1, 3, 7 }
  6                 no                  { 0, 1, 3, 7 }
  8                 no                  { 0, 1, 3, 7 }
  9                 no                  { 0, 1, 3, 7 }
 10                 yes                 { 0, 1, 3, 7, 10 }
 11                 no                  { 0, 1, 3, 7, 10 }
 12                 no                  { 0, 1, 3, 7, 10 }
 13                 no                  { 0, 1, 3, 7, 10 }
 14                 yes                 { 0, 1, 3, 7, 10, 14 }

This wasn't a complete accident - I chose three nodes for the initial clique that had larger than average augmented adjacency sets so that things weren't likely to peter out.

Copyright and Legal Notices

All Rights Reserved.