The Vertex Cover Problem is to find a subset of the vertices of a graph that contains an endpoint of every edge. For example, in the graph shown above, the subset (0, 1) highlighted in red is a vertex cover. The minimisation problem of finding the smallest vertex cover is NP-hard. However a good approximation can be achieved using a greedy algorithm. The algorithm is simply:

- While there are uncovered edges:
- Find the first uncovered edge
- Put one of its endpoints in the covering set
- Mark all of the edges incident upon that endpoint as covered

Below is an implementation in C. The function `vertex_cover()`

takes a graph in edge list format, its size (number of edges) and order (number of vertices), and the address of a pointer through which to return the covering set as an out parameter. The return value is the size of the covering set.

#include <stdlib.h> typedef struct { unsigned int first; unsigned int second; } edge; unsigned int vertex_cover(const edge *edges, unsigned int size, unsigned int order, unsigned int **cover) { unsigned int uncovered_size = size; unsigned int cover_size = 0; unsigned int *covered = calloc(size, sizeof(unsigned int)); *cover = calloc(order, sizeof(unsigned int)); if (covered == NULL || cover == NULL) { free(covered); free(*cover); *cover = NULL; return 0; } while (uncovered_size > 0) { unsigned int e, v; /* Find the first edge that hasn't been covered */ for (e = 0; e < size && covered[e] == 1; e++); /* Add its first endpoint to the covering set */ v = edges[e].first; (*cover)[v] = 1; cover_size++; /* Mark all uncovered edges containing its first endpoint as covered */ for (e = 0; e < size; e++) { if (!covered[e] && (edges[e].first == v || edges[e].second == v)) { covered[e] = 1; uncovered_size--; } } } free(covered); return cover_size; }

Here is an example program that finds a vertex cover on the graph shown above:

#include <stdio.h> #include <stdlib.h> /* Connect two edges */ void edge_connect(edge *edges, unsigned int first, unsigned int second, unsigned int *pos) { edges[*pos].first = first; edges[*pos].second = second; (*pos)++; } int main(void) { const unsigned int size = 4; /* Edges */ const unsigned int order = 5; /* Vertices */ edge *edges = malloc(size * sizeof(edge)); unsigned int i = 0; edge_connect(edges, 0, 1, &i); edge_connect(edges, 0, 2, &i); edge_connect(edges, 0, 3, &i); edge_connect(edges, 1, 4, &i); unsigned int *cover; unsigned int c = vertex_cover(edges, size, order, &cover); printf("Cover size is %u\n", c); printf("Vertices in cover:\n"); for (i = 0; i < order; i++) { if (cover[i]) { printf("%u ", i); } } putchar('\n'); free(edges); free(cover); return 0; }

The output:

Cover size is 2 Vertices in cover: 0 1