Vertex Cover

A vertex cover of a graph \(G\) is a set of vertices, \(V_c\), such that every edge in \(G\) has at least one of vertex in \(V_c\) as an endpoint. This means that every vertex in the graph is touching at least one edge. Vertex cover is a topic in graph theory that has applications in matching problems and optimization problems. A vertex cover might be a good approach to a problem where all of the edges in a graph need to be included in the solution.

Say you have an art gallery with many hallways and turns. Your gallery is displaying very valuable paintings, and you want to keep them secure. You are planning to install security cameras in each hallway so that the cameras have every painting in view. If there is a security camera in a hallway, it can see every painting in the hallway. If there is a camera in the corner where two hallways meet (the turn), it can view paintings in both hallways. We can model this system as a graph where the nodes represent the places where the hallways meet or when a hallway becomes a dead end, and the edges are the hallways.

In this graph, show where you would place the cameras such that all paintings are covered — this is a vertex cover! (There are many solutions).

Show Answer

There are many possible solutions — here are a few.

The first is a trivial solution — have cameras at all of the nodes. By definition, this is a vertex cover since all of the edges in graph must be connected to at least one of the vertices in the cover.

A vertex cover of a graph \(G\) is a set, \(V_c\), of vertices in \(G\) such that every edge of \(G\) has at least one of vertex in \(V_c\) as an endpoint. This means that every vertex in the graph is touching at least one edge. Vertex cover is an NP problem because any solution can be verified in polytime with \(n^2\) examinations of all the edges to see if their endpoints are included in the proposed vertex cover.

Here are images showing vertex cover. Each of the red vertices in the graphs make up the graph's vertex cover. The set of all red nodes in each graph touch every edge in the graph.

^[1]

It can be shown that vertex cover is NP-complete by showing that 3SAT is reducible to vertex cover (and by the Cook-Levin Theorem, this proves NP-completeness). In bipartite graphs, however, a vertex cover may be found in polynomial time.

The vertex covering number also called the minimum vertex covering number is the size of the smallest vertex cover of \(G\) and is denoted \(\tau(G)\).

Here are some examples of minimum vertex covers where the nodes in the minimum vertex cover are red.

^[2]

Finding a smallest vertex cover is classical optimization problem and is an NP-hard problem. In fact, the vertex cover problem was one of Karp's 21 NP-complete problems and is therefore a classical NP-complete problem in complexity theory.

For instance, in the example in the introduction with the security cameras, perhaps the gallery owner wants to minimize the cost of installing the camera and therefore wants to buy as few as possible, while still covering all of the paintings. In this case, a minimum vertex cover would be needed.

There are several algorithms for determining a vertex cover. Here's a psuedocode description of an algorithm that gives an approximate vertex cover using ideas from matching and greedy algorithms. Because the vertex cover problem is NP-complete finding an exact answer is very difficult and time consuming. Many times, approximation algorithms are useful. These run much faster than exact algorithms, but may produce a suboptimal solution. Here is an approximation algorithm for vertex cover.

1
2
3
4
5
6
7

def greedy(E, V)
C = {}
while E not empty:
    select any edge with endpoints (u,v) from E
    add (u,v) to C
    remove all edges incident to u or v from E
return C

Basically, the algorithm works by finding a maximal matching in \(G\) and adding at least one endpoint of each edge to the covering set of vertices \(C\). The optimal answer will contain one vertex from each edge in the matching, but a suboptimal covering could contain both endpoints from each edge, so the covering set \(C\) could be as much as two times as big as the optimal answer. This algorithm can be adapted to handle weighted graphs.

This is a polynomial time approximation algorithm (since it isn't guaranteed to return the optimal vertex cover) that runs in \(O(V + E)\) time.

Some problems that use ideas of vertex cover have additional and/or modified constraints compared to vertex cover. Below is a problem that uses a fairly straight-forward vertex cover approach.

The Traveling Salesperson Problem

The traveling salesperson problem is a classic computer science problem discussed in graph theory and complexity theory — especially when talking about NP-complete problems. The traveling salesperson problem goes like this:

A salesperson needs to visit a set of cities to sell their goods. They know how many cities they need to go to and the distances between each city. In what order should the salesperson visit each city exactly once so that they minimize their travel time and so that they end their journey in their city of origin?

Here's an example of the traveling salesperson problem where the salesperson needs to travel from the origin city to three other cities and then back to the origin. The salesperson must take roads that have fees associated with them, and they want to minimize the cost of their journey — so they need to find the path with the least edge weight.

1. , M. Vertex-cover.svg. Retrieved July 3, 2016, from https://en.wikipedia.org/wiki/File:Vertex-cover.svg
2. , M. Minimum-vertex-cover.svg. Retrieved July 3, 2016, from https://en.wikipedia.org/wiki/File:Minimum-vertex-cover.svg