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).

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\):
3. 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