Maximal matchings and the construction of cliques

A matching is a set of edges that do not have an end-node in common.

A maximal matching is a matching such that adding any edge in the graph that is not already in the matching would force an end-node to be shared, making the resulting object a non-matching.

Several years ago, I was playing with graphs when a friend passed on a suggestion that I consider using maximal matchings in my graph work. I hadn't heard of maximal matchings, looked them up, and played with them for a while.

Rather than talking about the edges of the complement of a graph, I like to talk about and work with the non-edges of a graph.

I wanted to see what would happen if I came up with a 'maximal matching' of the non-edges of a graph G (more properly, a maximal matching of the edges of the complement of G - I'll use maximal matching without the quotes from now on).

We can construct a maximal matching M of the non-edges of G by adding one non-edge F of G at a time to M (subject to the condition that no end-node of F is an end-node of a non-edge already in M) until no further non-edges of can be added to M (either there are no non-edges of G that are not in M, or every non-edge not in M shares at least one end-node with a non-edge in M.

We add non-edges of G to M in a different order, and we'll most likely end up with a different maximal matching of the non-edges of G, possibly having a different size.

The interesting thing is this: What can we say about the nodes that are not end-nodes of non-edges in M (which we'll denote as the set C)?

If there are at at least two nodes in C, they form a clique.

The proof is straightforward:

• Assume that M is a maximal matching of the non-edges of G.
• Assume that the set C consists of the nodes of G that are not the end-nodes of any non-edge in M and that C contains at least two nodes.
• Assume that that the nodes in C are not a clique of G. [The opposite of what we are trying to prove]
• Then there exists two nodes in C, X and Y, such that there is not an edge between X and Y.
• (X, Y) is non-edge of G that is not in M.
• Neither X or Y is the end-node of a non-edge in M, since they are both in C.
• (X, Y) can be added to M without violating the no-common-end-nodes condition.
• Therefore, M is not a maximal matching, violating one of our assumptions, and completing the proof by contradiction. Q.E.D.

If C contains only a single node, it is a 1-clique by definition.

Therefore, we can sharpen our statement: If C contains any nodes, they are a clique of G.

What does this give us? A simple and efficient way of constructing a clique of G that may be larger than what we would obtain by merely guessing.

An algorithm for constructing a clique of a graph by constructing a maximal matching of the non-edges of that graph

void
ConstructGraphThroughMaximalMatching( IN   Graph &   graph,
                                      OUT  Set &     clique )
{
    Set   nodesParticipatingInMaximalMatching;
    
    foreach ( Graph::NonEdge nonEdge in graph.NonEdges )
    {
        if ( ! nodesParticipatingInMaximalMatching.Contains( nonEdge.Node1 )  && 
             ! nodesParticipatingInMaximalMatching.Contains( nonEdge.Node2 ) )
        {
            nodesParticipatingInMaximalMatching.AddElement( nonEdge.Node1 );
            nodesParticipatingInMaximalMatching.AddElement( nonEdge.Node2 );
        }
    }

    clique = graph.Nodes;
    clique.DifferenceWith( nodesParticipatingInMaximalMatching );
}

An example

Let the non-edges of graph G be { {0, 3}, {1, 3}, {1, 4}, {1, 8}, {2, 4},
                                  {2, 5}, {4, 6}, {5, 9}, {8, 9} }.

Add {0, 3} to M, resulting in M: { {0, 3} }
Add {1, 4} to M, resulting in M: { {0, 3}, {1, 4} }
Add {2, 5} to M, resulting in M: { {0, 3}, {1, 4}, {2, 5} }

That's it.

The other non-edges have at least one end-node in { 0, 1, 2, 3, 4, 5 }, 
the set of nodes participating in M.

The nodes of G is the set { 0, 1, 2, 3, 4, 5, 6, 7, 8, 9 }.

The nodes of G that do not partipate in M is { 6, 7, 8, 9 }.

One clique of G, therefore, is { 6, 7, 8, 9 }.

This clique can be maximalized into { 0, 2, 6, 7, 8, 9 }, another clique of G.

At least one interesting issue remains for this topic: How do we sequence the addition of non-edges to M so as to minimize the number of non-edges in M and maximize the number of nodes that do not participate in M (the nodes in C)?

Tomorrow, I'll talk about the maximalization of cliques.

Copyright and Legal Notices

All Rights Reserved.