The k-Reduction of Graphs

Introduction

I mentioned elsewhere that reduction is one of my favorite and most effective techniques.

One problem which cries out for the application of reductive techniques is the k-Clique Exists problem, in which we need to determine whether a graph contains a clique (complete subgraph) of size k.

This problem is so amenable to reduction because any node or edge that can be shown not to participate in a k-clique can be removed from the graph without interfering with our ability to solve the problem. In fact, getting rid of the 'clutter' may help us to solve the problem more efficiently. Also, as occurs in my search approach to the k-Clique Exists problem, the search space can be reduced in a similar way.

k-reduction is a family of algorithms for removing elements of a graph (i.e. nodes and edges) that can not participate in a k-clique. These algorithms may be grouped into different levels - the higher the level, the more work is usually required and the great the maximum amount of reduction.

I haven't given much thought about how to classify these algorithms to level above the first two levels, but that may change once I revisit the use of sweeps in k-reduction, which I'll do over the next week or so.

Level 1 contains a single type of algorithm, one that removes nodes and incident edges from a graph until all nodes in the graph have degree of k-1 or more. It removes nodes that are not k-sufficient until all nodes in the graph are k-sufficient.

Level 2 contains algorithms that ensure that both surviving nodes and surviving edges are k-sufficient. In particular, any node that has degree less than k-1 is deleted, any edge that is incident with a deleted node is removed, as is any edge between nodes X and Y for which the augmented adjacency set AAS(X) intersected with the AAS(Y) has cardinality of less than k.

I'll give more thought about how to classify these k-reduction algorithms later, once I've reviewed work that I've done in the past and have given this more thought.

A straightforward level-2 k-reduction algorithm is presented below. It has three outcomes: a k-clique exists, a k-clique does not exist, and the graph has been k-reduced without resolving the question of k-clique existence. An example of the application of this algorithm to a graph follows.

This algorithm can be improved upon and I have worked with several variations of it. I present this version for clarity. The helper function ContainsKClique follows the KReduceGraph function.

As before, I've presented code in a casual C++ that has been augmented by foreach and properties, which I borrowed from C#.

A simple algorithm for the k-reduction of a graph

//  This algorithm's goal is to k-reduce a graph within the context of 
//  determining whether the graph contains a clique of size k.  Once this has
//  been determined, the further k-reduction of the graph is not pursued.

enum Outcome = { keKCliqueDoesNotExist, keKCliqueExists, keKReduced };

Outcome
KReduceGraph( IN   const int   k,
              IN   Graph &     graph,
              OUT  Set &       exemplarClique )
{
    if ( graph.Nodes.Cardinality < k )
    {
        return keKCliqueDoesNotExist;
    }
    else if ( graph.Nodes.Cardinality == k )
    {
        if ( ContainsKClique( graph.Nodes, k, graph ) )
        {
            exemplarClique = graph.Nodes;

            return keKCliqueExists;
        }
        else
        {
            return keKCliqueDoesNotExist;
        }
    }

    Set  nodesToCheck  =  graph.Nodes;

    do
    {
        foreach ( int node1 in nodesToCheck )
        {
            Set *   pAAS1  =  graph.AugmentedAdjacencySet[node1];

            if ( pAAS1->Cardinality >= k )
            {
                foreach ( int node2 in *pAAS1 )
                {
                    Set *   pAAS2  =  graph.AugmentedAdjacencySet[node2];

                    Set     intersection  =  *pAAS1;

                    intersection.IntersectWith( *pAAS2 );

                    if ( intersection.Cardinality < k )
                    {
                        pAAS1->RemoveElement( node2 );
                        pAAS2->RemoveElement( node1 );

                        nodesToCheck.AddElement( node1 );
                        nodesToCheck.AddElement( node2 );
                    }
                    else if ( intersection.Cardinality == k )
                    {
                        if ( ContainsKClique( intersection, k, graph ) )
                        {
                            exemplarClique = intersection;

                            return keKCliqueExists;
                        }
                        else
                        {
                            pAAS1->RemoveElement( node2 );
                            pAAS2->RemoveElement( node1 );

                            nodesToCheck.AddElement( node1 );
                            nodesToCheck.AddElement( node2 );
                        }
                    }
            }
            else if ( pAAS1->Cardinality == k )
            {
                if ( ContainsKClique( *pAAS1, k, graph ) )
                {
                    exemplarClique = *pAAS1;

                    return keKCliqueExists;
                }
                else
                {
                    return keKCliqueDoesNotExist;
                }
            }
            else
            {
                nodesToCheck.UnionWith( *pAAS1 );

                DeleteNode( *pAAS1 );

                if ( graph.Nodes.Cardinality < k )
                {
                    return keKCliqueDoesNotExist;
                }
                else if ( graph.Nodes.Cardinality == k )
                {
                    if ( ContainsKClique( graph.Nodes, k, graph ) )
                    {
                        setExemplarClique = graph.Nodes;

                        return keKCliqueExists;
                    }
                    else
                    {
                        return keKCliqueDoesNotExist;
                    }
                }
            }
        }
    }
    while ( nodesToCheck.Cardinality > 0 );

    return keKReduced;
}

bool
ContainsKClique( IN  Set &       nodes,
                 IN  const int   k,
                 IN  Graph &     graph )
{
    Set   intersection;

    intersection.SetAllElements();

    foreach ( int node in nodes )
    {
        intersection.IntersectWith( graph.AugmentedAdjacencySet[node] );

        if ( intersection.Cardinality < k )
        {
            return false;
        }
    }

    return true;
}

An example - An application of this algorithm to a graph

Graph generation parameters

    number of nodes         =  25
    probability of an edge  =  0.63

Augmented Adjacency Sets for the Original Graph

0 : { 0, 1, 2, 4, 5, 6, 7, 11, 12, 14, 15, 16, 18, 19, 20, 21, 23 }
1 : { 0, 1, 3, 4, 6, 10, 11, 13, 17, 18, 23 }
2 : { 0, 2, 4, 5, 7, 8, 9, 10, 11, 12, 15, 17, 18, 19, 21, 22, 23 }
3 : { 1, 3, 4, 5, 6, 7, 9, 10, 12, 16, 17, 20 }
4 : { 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 11, 13, 14, 15, 16, 17, 18, 19, 20, 22, 23, 24 }
5 : { 0, 2, 3, 4, 5, 8, 10, 12, 13, 15, 16, 17, 18, 19, 20, 23, 24 }
6 : { 0, 1, 3, 4, 6, 7, 10, 12, 13, 14, 15, 16, 18, 20, 21, 23, 24 }
7 : { 0, 2, 3, 4, 6, 7, 8, 9, 10, 11, 13, 14, 15, 16, 17, 19, 21, 22, 23, 24 }
8 : { 2, 4, 5, 7, 8, 9, 11, 12, 14, 15, 17, 18, 19, 20, 21, 22, 24 }
9 : { 2, 3, 4, 7, 8, 9, 10, 11, 15, 18, 20, 21, 22 }
10 : { 1, 2, 3, 5, 6, 7, 9, 10, 11, 14, 21, 22, 23, 24 }
11 : { 0, 1, 2, 4, 7, 8, 9, 10, 11, 12, 13, 15, 22, 24 }
12 : { 0, 2, 3, 5, 6, 8, 11, 12, 13, 14, 16, 19, 23, 24 }
13 : { 1, 4, 5, 6, 7, 11, 12, 13, 14, 16, 17, 18, 19, 21, 22, 24 }
14 : { 0, 4, 6, 7, 8, 10, 12, 13, 14, 15, 17, 19, 20, 21, 24 }
15 : { 0, 2, 4, 5, 6, 7, 8, 9, 11, 14, 15, 16, 19, 23, 24 }
16 : { 0, 3, 4, 5, 6, 7, 12, 13, 15, 16, 18, 19, 20, 21, 22 }
17 : { 1, 2, 3, 4, 5, 7, 8, 13, 14, 17, 18, 19, 21, 24 }
18 : { 0, 1, 2, 4, 5, 6, 8, 9, 13, 16, 17, 18, 19, 20, 21, 22, 24 }
19 : { 0, 2, 4, 5, 7, 8, 12, 13, 14, 15, 16, 17, 18, 19, 21, 22, 23, 24 }
20 : { 0, 3, 4, 5, 6, 8, 9, 14, 16, 18, 20, 22, 24 }
21 : { 0, 2, 6, 7, 8, 9, 10, 13, 14, 16, 17, 18, 19, 21, 22, 23, 24 }
22 : { 2, 4, 7, 8, 9, 10, 11, 13, 16, 18, 19, 20, 21, 22 }
23 : { 0, 1, 2, 4, 5, 6, 7, 10, 12, 15, 19, 21, 23 }
24 : { 4, 5, 6, 7, 8, 10, 11, 12, 13, 14, 15, 17, 18, 19, 20, 21, 24 }


k = 8


at top of main loop
   removing edge (  0 -  1 )   the AASs of the two nodes have 7 nodes in common
   removing edge (  0 - 11 )   the AASs of the two nodes have 7 nodes in common
   removing edge (  1 -  3 )   the AASs of the two nodes have 6 nodes in common
   removing edge (  1 -  6 )   the AASs of the two nodes have 7 nodes in common
   removing edge (  1 - 10 )   the AASs of the two nodes have 4 nodes in common
   removing edge (  1 - 11 )   the AASs of the two nodes have 4 nodes in common
   removing edge (  1 - 13 )   the AASs of the two nodes have 5 nodes in common
   removing edge (  1 - 17 )   the AASs of the two nodes have 4 nodes in common
   removing edge (  1 - 18 )   the AASs of the two nodes have 3 nodes in common
   removing edge (  1 - 23 )   the AASs of the two nodes have 3 nodes in common
   removing edge (  3 -  9 )   the AASs of the two nodes have 6 nodes in common
   removing edge (  3 - 10 )   the AASs of the two nodes have 5 nodes in common
   removing edge (  3 - 12 )   the AASs of the two nodes have 5 nodes in common
   removing edge (  3 - 16 )   the AASs of the two nodes have 7 nodes in common
   removing edge (  3 - 17 )   the AASs of the two nodes have 5 nodes in common
   removing edge (  3 - 20 )   the AASs of the two nodes have 5 nodes in common
   removing edge (  4 -  1 )   the AASs of the two nodes have 2 nodes in common
   removing edge (  4 -  3 )   the AASs of the two nodes have 5 nodes in common
   removing edge (  5 -  3 )   the AASs of the two nodes have 2 nodes in common
   removing edge (  5 - 10 )   the AASs of the two nodes have 5 nodes in common
   removing edge (  6 -  3 )   the AASs of the two nodes have 3 nodes in common
   removing edge (  6 - 10 )   the AASs of the two nodes have 7 nodes in common
   removing edge (  7 -  3 )   the AASs of the two nodes have 2 nodes in common
   removing edge (  9 - 10 )   the AASs of the two nodes have 7 nodes in common
   removing edge (  9 - 15 )   the AASs of the two nodes have 7 nodes in common
   removing edge (  9 - 20 )   the AASs of the two nodes have 6 nodes in common
   removing edge (  9 - 21 )   the AASs of the two nodes have 7 nodes in common
   removing edge ( 10 -  2 )   the AASs of the two nodes have 7 nodes in common
   removing edge ( 10 - 11 )   the AASs of the two nodes have 5 nodes in common
   removing edge ( 10 - 14 )   the AASs of the two nodes have 5 nodes in common
   removing edge ( 10 - 21 )   the AASs of the two nodes have 6 nodes in common
   removing edge ( 10 - 22 )   the AASs of the two nodes have 3 nodes in common
   removing edge ( 10 - 23 )   the AASs of the two nodes have 3 nodes in common
   removing edge ( 10 - 24 )   the AASs of the two nodes have 3 nodes in common
   removing edge ( 11 -  9 )   the AASs of the two nodes have 7 nodes in common
   removing edge ( 11 - 12 )   the AASs of the two nodes have 6 nodes in common
   removing edge ( 11 - 13 )   the AASs of the two nodes have 6 nodes in common
   removing edge ( 11 - 15 )   the AASs of the two nodes have 7 nodes in common
   removing edge ( 11 - 22 )   the AASs of the two nodes have 6 nodes in common
   removing edge ( 11 - 24 )   the AASs of the two nodes have 5 nodes in common
   removing edge ( 12 -  2 )   the AASs of the two nodes have 7 nodes in common
   removing edge ( 12 -  8 )   the AASs of the two nodes have 6 nodes in common
   removing edge ( 12 - 14 )   the AASs of the two nodes have 7 nodes in common
   removing edge ( 12 - 16 )   the AASs of the two nodes have 7 nodes in common
   removing edge ( 12 - 19 )   the AASs of the two nodes have 7 nodes in common
   removing edge ( 12 - 23 )   the AASs of the two nodes have 5 nodes in common
   removing edge ( 12 - 24 )   the AASs of the two nodes have 5 nodes in common
   removing edge ( 13 - 12 )   the AASs of the two nodes have 4 nodes in common
   removing edge ( 14 - 20 )   the AASs of the two nodes have 7 nodes in common
   removing edge ( 18 -  9 )   the AASs of the two nodes have 6 nodes in common
   removing edge ( 20 -  0 )   the AASs of the two nodes have 7 nodes in common
   removing edge ( 20 -  5 )   the AASs of the two nodes have 7 nodes in common
   removing edge ( 20 -  6 )   the AASs of the two nodes have 6 nodes in common
   removing edge ( 20 -  8 )   the AASs of the two nodes have 6 nodes in common
   removing edge ( 20 - 16 )   the AASs of the two nodes have 5 nodes in common
   removing edge ( 20 - 18 )   the AASs of the two nodes have 5 nodes in common
   removing edge ( 20 - 20 )   the AASs of the two nodes have 4 nodes in common
   removing edge ( 20 - 22 )   the AASs of the two nodes have 2 nodes in common
   removing edge ( 20 - 24 )   the AASs of the two nodes have 2 nodes in common
   removing edge ( 21 - 23 )   the AASs of the two nodes have 7 nodes in common
   removing edge ( 22 -  9 )   the AASs of the two nodes have 6 nodes in common
   removing edge ( 23 -  5 )   the AASs of the two nodes have 7 nodes in common
   removing edge ( 23 -  6 )   the AASs of the two nodes have 6 nodes in common
   removing edge ( 23 -  7 )   the AASs of the two nodes have 7 nodes in common
   removing edge ( 23 - 15 )   the AASs of the two nodes have 6 nodes in common
   removing edge ( 23 - 19 )   the AASs of the two nodes have 5 nodes in common
   removing edge ( 23 - 23 )   the AASs of the two nodes have 4 nodes in common
at top of main loop
   removing edge (  0 - 12 )   the AASs of the two nodes have 4 nodes in common
   removing edge (  0 - 23 )   the AASs of the two nodes have 3 nodes in common
   deleting node 1  -  its AAS has cardinality 1
      removing edge ( 1 - 1 )
   removing edge (  2 -  9 )   the AASs of the two nodes have 5 nodes in common
   removing edge (  2 - 11 )   the AASs of the two nodes have 5 nodes in common
   removing edge (  2 - 23 )   the AASs of the two nodes have 2 nodes in common
   deleting node 3  -  its AAS has cardinality 1
      removing edge ( 3 - 3 )
   removing edge (  5 - 12 )   the AASs of the two nodes have 2 nodes in common
   removing edge (  6 - 12 )   the AASs of the two nodes have 2 nodes in common
   removing edge (  7 -  9 )   the AASs of the two nodes have 4 nodes in common
   removing edge (  7 - 10 )   the AASs of the two nodes have 2 nodes in common
   removing edge (  7 - 11 )   the AASs of the two nodes have 4 nodes in common
   removing edge (  8 -  9 )   the AASs of the two nodes have 3 nodes in common
   removing edge (  8 - 11 )   the AASs of the two nodes have 3 nodes in common
   deleting node 9  -  its AAS has cardinality 2
      removing edge ( 9 - 4 )
      removing edge ( 9 - 9 )
   deleting node 12  -  its AAS has cardinality 1
      removing edge ( 12 - 12 )
at top of main loop
   removing edge (  4 - 11 )   the AASs of the two nodes have 2 nodes in common
   removing edge (  4 - 20 )   the AASs of the two nodes have 1 nodes in common
   removing edge (  4 - 23 )   the AASs of the two nodes have 1 nodes in common
   deleting node 10  -  its AAS has cardinality 1
      removing edge ( 10 - 10 )
   deleting node 11  -  its AAS has cardinality 1
      removing edge ( 11 - 11 )
   deleting node 23  -  its AAS has cardinality 0
at top of main loop
   deleting node 20  -  its AAS has cardinality 0


Augmented Adjacency Sets for the k-Reduced Graph

0 : { 0, 2, 4, 5, 6, 7, 14, 15, 16, 18, 19, 21 }
2 : { 0, 2, 4, 5, 7, 8, 15, 17, 18, 19, 21, 22 }
4 : { 0, 2, 4, 5, 6, 7, 8, 13, 14, 15, 16, 17, 18, 19, 22, 24 }
5 : { 0, 2, 4, 5, 8, 13, 15, 16, 17, 18, 19, 24 }
6 : { 0, 4, 6, 7, 13, 14, 15, 16, 18, 21, 24 }
7 : { 0, 2, 4, 6, 7, 8, 13, 14, 15, 16, 17, 19, 21, 22, 24 }
8 : { 2, 4, 5, 7, 8, 14, 15, 17, 18, 19, 21, 22, 24 }
13 : { 4, 5, 6, 7, 13, 14, 16, 17, 18, 19, 21, 22, 24 }
14 : { 0, 4, 6, 7, 8, 13, 14, 15, 17, 19, 21, 24 }
15 : { 0, 2, 4, 5, 6, 7, 8, 14, 15, 16, 19, 24 }
16 : { 0, 4, 5, 6, 7, 13, 15, 16, 18, 19, 21, 22 }
17 : { 2, 4, 5, 7, 8, 13, 14, 17, 18, 19, 21, 24 }
18 : { 0, 2, 4, 5, 6, 8, 13, 16, 17, 18, 19, 21, 22, 24 }
19 : { 0, 2, 4, 5, 7, 8, 13, 14, 15, 16, 17, 18, 19, 21, 22, 24 }
21 : { 0, 2, 6, 7, 8, 13, 14, 16, 17, 18, 19, 21, 22, 24 }
22 : { 2, 4, 7, 8, 13, 16, 18, 19, 21, 22 }
24 : { 4, 5, 6, 7, 8, 13, 14, 15, 17, 18, 19, 21, 24 }


Augmented Adjacency Sets for the Original Graph

0 : { 0, 1, 2, 4, 5, 6, 7, 11, 12, 14, 15, 16, 18, 19, 20, 21, 23 }
1 : { 0, 1, 3, 4, 6, 10, 11, 13, 17, 18, 23 }
2 : { 0, 2, 4, 5, 7, 8, 9, 10, 11, 12, 15, 17, 18, 19, 21, 22, 23 }
3 : { 1, 3, 4, 5, 6, 7, 9, 10, 12, 16, 17, 20 }
4 : { 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 11, 13, 14, 15, 16, 17, 18, 19, 20, 22, 23, 24 }
5 : { 0, 2, 3, 4, 5, 8, 10, 12, 13, 15, 16, 17, 18, 19, 20, 23, 24 }
6 : { 0, 1, 3, 4, 6, 7, 10, 12, 13, 14, 15, 16, 18, 20, 21, 23, 24 }
7 : { 0, 2, 3, 4, 6, 7, 8, 9, 10, 11, 13, 14, 15, 16, 17, 19, 21, 22, 23, 24 }
8 : { 2, 4, 5, 7, 8, 9, 11, 12, 14, 15, 17, 18, 19, 20, 21, 22, 24 }
9 : { 2, 3, 4, 7, 8, 9, 10, 11, 15, 18, 20, 21, 22 }
10 : { 1, 2, 3, 5, 6, 7, 9, 10, 11, 14, 21, 22, 23, 24 }
11 : { 0, 1, 2, 4, 7, 8, 9, 10, 11, 12, 13, 15, 22, 24 }
12 : { 0, 2, 3, 5, 6, 8, 11, 12, 13, 14, 16, 19, 23, 24 }
13 : { 1, 4, 5, 6, 7, 11, 12, 13, 14, 16, 17, 18, 19, 21, 22, 24 }
14 : { 0, 4, 6, 7, 8, 10, 12, 13, 14, 15, 17, 19, 20, 21, 24 }
15 : { 0, 2, 4, 5, 6, 7, 8, 9, 11, 14, 15, 16, 19, 23, 24 }
16 : { 0, 3, 4, 5, 6, 7, 12, 13, 15, 16, 18, 19, 20, 21, 22 }
17 : { 1, 2, 3, 4, 5, 7, 8, 13, 14, 17, 18, 19, 21, 24 }
18 : { 0, 1, 2, 4, 5, 6, 8, 9, 13, 16, 17, 18, 19, 20, 21, 22, 24 }
19 : { 0, 2, 4, 5, 7, 8, 12, 13, 14, 15, 16, 17, 18, 19, 21, 22, 23, 24 }
20 : { 0, 3, 4, 5, 6, 8, 9, 14, 16, 18, 20, 22, 24 }
21 : { 0, 2, 6, 7, 8, 9, 10, 13, 14, 16, 17, 18, 19, 21, 22, 23, 24 }
22 : { 2, 4, 7, 8, 9, 10, 11, 13, 16, 18, 19, 20, 21, 22 }
23 : { 0, 1, 2, 4, 5, 6, 7, 10, 12, 15, 19, 21, 23 }
24 : { 4, 5, 6, 7, 8, 10, 11, 12, 13, 14, 15, 17, 18, 19, 20, 21, 24 }

Copyright and Legal Notices

All Rights Reserved.