## Complement of a graph

The *complement* of a graph is another graph in which all vertices that are adjacent in the original graph are not adjacent, and all vertices that are not adjacent in the original graph are adjacent. The picture above shows a graph and its complement. Notice that vertex 4, which is adjacent to all of the other vertices in the original graph is adjacent to none in the complement graph, while vertices 0 and 1, which have 3 out of a possible 4 neighbours in the original graph have 4 – 3 = 1 neighbours in the complement graph.

Computing the complement of a graph is easy – just change every 0 in the adjacency matrix to a 1 and every 1 to a 0. Below is how it looks in C. I am assuming the graph is a simple graph and so does not have any self-loops (vertices that are adjacent to themselves), so I am ignoring the central diagonal.

void complement(unsigned int *const *adjmat, unsigned int order) { unsigned int i, j; for (i = 0; i < order;i++) { for (j = 0; j < order; j++) { if (i != j) { adjmat[i][j] = !adjmat[i][j]; } } } }

## Cliques and independent sets

Recall that a *clique* in a graph is a subset of the vertices in which *all* of the vertices are adjacent to each other, while an *independent set* is a subset of the vertices in which *none of* the vertices are adjacent to each other. This means that cliques in a graph become independent sets in its complement, and vice-versa. For example, in the picture above, the clique (1, 2, 4) shown in red becomes the independent set (1, 2, 4) in the complement graph.

In a previous post I presented a backtracking algorithm for solving the Maximum Clique problem – finding the largest clique in a graph. The dual of this problem is the Maximum Independent Set problem – finding the largest independent set in a graph. Because of the duality of cliques and independent sets through taking the graph’s complement, this means that having a Max Clique function gives us a Max Independent Set function for free – we just need to take the graph’s complement and then solve the Max Clique Problem, as below:

unsigned int maximum_independent_set(unsigned int *const *adjmat, unsigned int order, unsigned int **max_set) { unsigned int max_clique_size; complement(adjmat, order); max_clique_size = maximum_clique((const unsigned int **)adjmat, order, max_set); complement(adjmat, order); return max_clique_size; }

Here is an example program that finds a maximum independent set in the second graph shown above:

#include <stdio.h> #include <stdlib.h> int main(void) { const unsigned int order = 5; /* Vertices */ unsigned int r1[] = {0, 0, 1, 0, 0}; unsigned int r2[] = {0, 0, 0, 1, 0}; unsigned int r3[] = {1, 0, 0, 1, 0}; unsigned int r4[] = {0, 1, 1, 0, 0}; unsigned int r5[] = {0, 0, 0, 0, 0}; unsigned int *const adjmat[] = {r1, r2, r3, r4, r5}; unsigned int *max_set; unsigned int max_size, i; max_size = maximum_independent_set(adjmat, order, &max_set); printf("Max independent set size is %u\n", max_size); for (i = 0; i < order; i++) { if (max_set[i] == 1) { printf("%u ", i); } } putchar('\n'); free(max_set); return 0; }

The output:

Max independent set size is 3 1 2 4