An Algorithm to find a Minimum Vertex Cover in a Graph with an Implementation in Rust.

The minimum vertex cover of a graph is a set of vertexes of minimal size such that every edge in the graph shares at least one vertex with it. So, if C is such a cover and you pick any edge e = {u, v}, then u or v are within C. Moreover, no other set with this property has a size less than that of C.

In graph theory there are some famous theorems about so called matchings that make use of the minimum vertex covers (see here). Also, without going into details, like many concepts of graph theory its list of real-world applications is huge.

Though, the problem is known to be NP-hard and so it is uncertain to ever find an algorithm operating better than with exponential complexity. In this story we solely focus on solving the exact problem without concerning about its complexity. A quite straightforward approach is given in the next section.

Algorithm:

We are going to create recursively a vertex cover C of minimum size and start with an empty set of vertexes. Since at start, we do not know which vertex an optimal solution contains, we have to write the algorithm such that all the possible vertexes will be checked to initiate C.

Adding some first vertex to C gives a potential cover. Let us assume C had been generated in previous steps by adding appropriate vertexes. The first what we do is to verify if C is a cover. The can be easily done by verifying that each edge of the graph shares a vertex with C. In case it does, we just return C to compare its size with other generated covers. In case not, we figure out the edges of the graph that have no vertex in common with C and take the set of its vertexes as potential new members for C.

For each such potential new member we create a new cover C_new, and recursively extend C_new to a vertex cover but with at less as possible vertexes. Since we do this for all the above potential new members, we obtain a set of such optimized vertex covers. Though, each has been generated based on a different C_new. Now, among these covers, we pick the one with lowest size and return it.

The above steps delivers the minimum vertex cover that can be built from extending the given vertex set C. At the…