Tag Archives: Maximum Independent Set

Complement of a graph in C

A graph and its complement

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

Greedy Maximum Independent Set in C

An independent set of a graph is some subset of the vertices where no vertex in the subset is connected to another vertex in the subset. For example, in the graph shown below, the set of vertices (0, 2, 4) is an independent set, as is (1, 3, 5).
A wheel graph on 7 vertices showing an independent set
The Maximimum Independent Set (MIS) problem is to find an independent set with the greatest cardinality in a graph. The problem is NP-complete, but a greedy algorithm gives a good approximation.

The algorithm is:

  1. 1. Start with the set of vertices of the graph, \(V\) and an empty set for the MIS, \(S\)
  2. While \(V \ne \emptyset\):
    1. Find a vertex of minimum degree \(v \in V\)
    2. Add it to \(S\)
    3. Remove it and its neighbours from \(V\)

The following is an implementation in C;

#include <stdlib.h>

/* Graph edge */
typedef struct {
    unsigned int first;
    unsigned int second;
} edge;

/* State a vertex can be in */
typedef enum {
    IN_GRAPH = 0,
    IN_MIS = 1,
    DISCARDED = 2
} vertex_state;

/* Vertex info */
typedef struct {
    vertex_state state;
    unsigned int degree;
} vertex_info;

/* Create and initialise the data structure for vertices */
static vertex_info *create_vertices(const edge *edges, unsigned int size, 
        unsigned int order)
{
    unsigned int i;
    vertex_info *vertices = malloc(order * sizeof(vertex_info));
    if (vertices == NULL) {
        return 0;
    }
    for (i = 0; i < order; i++) {
        vertices[i].state = IN_GRAPH;
        vertices[i].degree = 0;
    }
    for (i = 0; i < size; i++) {
        vertices[edges[i].first].degree++;
        vertices[edges[i].second].degree++;
    }
    return vertices;
}

/* Find a vertex with the lowest degree of any in the graph */
static int min_degree_vertex(const vertex_info *vertices, unsigned int order)
{
    unsigned int min_degree = 0;
    int min_vertex = -1;
    unsigned int i;
    for (i = 0; i < order; i++) {
        if (vertices[i].state == IN_GRAPH 
                && (min_degree == 0 
                    || vertices[i].degree < min_degree))
        {
            min_degree = vertices[i].degree;
            min_vertex = i;
        }
    }
    return min_vertex;
}

/* Move a vertex from the graph, adjusting the degrees of its neighbours */
static void move_vertex(vertex_info *vertices, unsigned int order, const edge *edges,
        unsigned int size, unsigned int v, vertex_state state)
{
    unsigned int e;
    /* Remove vertex */
    vertices[v].state = state;
    /* Reduce the degrees of its neighbours */
    for (e = 0; e < size; e++) {
        if (edges[e].first == v
            && vertices[edges[e].second].state == IN_GRAPH) 
        {
                vertices[edges[e].second].degree--;
        }
        else if (edges[e].second == v
            && vertices[edges[e].first].state == IN_GRAPH) 
        {
            vertices[edges[e].first].degree--;
        }
    }
}

/* Create the MIS array from the vertices structure */
static unsigned int *create_mis(const vertex_info *vertices, unsigned int order,
        unsigned int m)
{
    unsigned int *mis = malloc(m * sizeof(unsigned int));
    if (mis) {
        unsigned int v, m = 0;
        for (v = 0; v < order; v++) {
            if (vertices[v].state == IN_MIS) {
                mis[m++] = v;
            }
        }
    }
    return mis;
}

unsigned int maximum_independent_set(const edge *edges, unsigned int size,
        unsigned int order, unsigned int **mis)
{
    unsigned int m = 0;
    vertex_info *vertices;
    unsigned int finished = 0;
    unsigned int i;

    /* Create vertices structure */
    vertices = create_vertices(edges, size, order);

    /* Main algorithm */
    while (!finished) {
        /* Find a vertex of minimum degree */
        int v = min_degree_vertex(vertices, order);
        if (v != -1) {
            /* Put it in the independent set */
            move_vertex(vertices, order, edges, size, v, IN_MIS);
            m++;
            /* Remove its neighbours from the graph */
            for (i = 0; i < size; i++) {
                if (edges[i].first == v
                        && vertices[edges[i].second].state == IN_GRAPH)
                {
                    move_vertex(vertices, order, edges, size, 
                            edges[i].second, DISCARDED);
                }
                else if (edges[i].second == v
                        && vertices[edges[i].first].state == IN_GRAPH)
                {
                    move_vertex(vertices, order, edges, size,
                            edges[i].first, DISCARDED);
                }
            }
        }
        else {
            finished = 1;
        } 
    }

    /* Create and populate MIS array */
    *mis = create_mis(vertices, order, m);
    if (*mis == NULL) {
        m = 0;
    }

    free(vertices);

    return m;
}

An example program to find an MIS in the graph shown above:

#include <stdio.h>
#include <stdlib.h>

/* Create a wheel graph of order n */
unsigned int wheel_graph(unsigned int n, edge **edges)
{
    const unsigned int size = 2 * n - 2;
    *edges = malloc(size * sizeof(edge));
    if (*edges != NULL) {
        /* Create the rim */
        unsigned int i;
        for (i = 0; i < n - 2; i++) {
            (*edges)[i].first = i;
            (*edges)[i].second = i + 1;
        }
        (*edges)[i].first = n - 2;
        (*edges)[i].second = 0;
        /* Create the spokes */
        for (i = 0; i < n - 1; i++) {
            (*edges)[n + i - 1].first = i;
            (*edges)[n + i - 1].second = n - 1;
        }
    }
    return size;
}

static void print_mis(const unsigned int *mis, size_t m)
{
    unsigned int i;
    for (i = 0; i < m; i++) {
        printf("%u ", mis[i]);
    }
    putchar('\n');
}

int main(void)
{
    unsigned int order = 7; /* Vertices */
    unsigned int *mis;
    edge *edges;
    unsigned int size = wheel_graph(order, &edges);
    unsigned m = maximum_independent_set(edges, size, order, &mis);
    print_mis(mis, m);
    free(mis);
    free(edges);
    return 0;
}

The output:

0 2 4