A clique in a graph is a subgraph in which all vertices are connected to each other – a complete subgraph. The Maximum Clique Problem is to find the largest clique of a graph. For example, in the graph shown above the maximum clique size is 3, and the vertices (1, 2, 4) are a maximum clique, as are (0, 1, 4) and (0, 3, 4).
The Maximum Clique Problem is NP-complete, but can be solved efficiently using backtracking. The following is a backtracking implementation in C. The function maximum_clique()
takes a graph in adjacency matrix form and its order (the number of vertices), and will return a maximum clique and its size.
#include <stdlib.h> #include <string.h> static void maximum_clique_recursive(const unsigned int **adjmat, unsigned int order, unsigned int *current_clique, unsigned int *current_clique_size, unsigned int *max_clique, unsigned int *max_clique_size, unsigned int level) { unsigned int i, connected; if (level == order) { /* Found a new max clique */ memcpy(max_clique, current_clique, order * sizeof(unsigned int)); *max_clique_size = *current_clique_size; return; } /* Find out if current vertex is connected to all vertices in current clique */ connected = 1; for (i = 0; i < level && connected; i++) { if (current_clique[i] && !adjmat[level][i]) { connected = 0; } } if (connected) { /* Add this vertex to the clique */ current_clique[level] = 1; (*current_clique_size)++; maximum_clique_recursive(adjmat, order, current_clique, current_clique_size, max_clique, max_clique_size, level + 1); (*current_clique_size)--; } if (*current_clique_size + order - level > *max_clique_size) { /* Still promising */ current_clique[level] = 0; maximum_clique_recursive(adjmat, order, current_clique, current_clique_size, max_clique, max_clique_size, level + 1); } } unsigned int maximum_clique(const unsigned int **adjmat, unsigned int order, unsigned int **max_clique) { unsigned int max_clique_size = 0; unsigned int current_clique_size = 0; unsigned int *current_clique = malloc(order * sizeof(unsigned int)); *max_clique = malloc(order * sizeof(unsigned int)); if (current_clique == NULL || *max_clique == NULL) { free(current_clique); free(max_clique); return 0; } maximum_clique_recursive(adjmat, order, current_clique, ¤t_clique_size, *max_clique, &max_clique_size, 0); free(current_clique); return max_clique_size; }
Here is an example program that finds a maximum clique on the graph shown at the top:
#include <stdio.h> #include <stdlib.h> int main() { const unsigned int order = 5; /* Vertices */ unsigned int r1[] = {0, 1, 0, 1, 1}; unsigned int r2[] = {1, 0, 1, 0, 1}; unsigned int r3[] = {0, 1, 0, 0, 1}; unsigned int r4[] = {1, 0, 0, 0, 1}; unsigned int r5[] = {1, 1, 1, 1, 0}; const unsigned int *adjmat[] = {r1, r2, r3, r4, r5}; unsigned int *max_clique; unsigned int max_clique_size = maximum_clique(adjmat, order, &max_clique); unsigned int i; printf("Max clique size is %u\n", max_clique_size); for (i = 0; i < order; i++) { if (max_clique[i] == 1) { printf("%u ", i); } } putchar('\n'); free(max_clique); return 0; }
The output:
Max clique size is 3 1 2 4