Under Construction: Consider this content a preview of the real thing which is coming soon (hopefully).
The formal definition of the vertex cover problem is: given an undirected graph $G = (V,E)$, find the subset $V^\prime \subseteq V$ such that if $(u,v) \in E$, then $u \in V^\prime$ or $v \in V^\prime$ (or both). In plain English: find the smallest set of vertices in an undirected graph that include at least one end of each edge in the graph. The size of a vertex cover is the number of included vertices. Consider the example below:
The vertex cover is the set because that is the smallest set of vertices that includes at least one end of every edge in the graph.
Unfortunately, the vertex cover problem is $NP$-hard so it’s not possible to create an efficient algorithm capable of solving the general case. However, there are several reasonable approaches to the problem including:
- Solve for the special case
- If approximate answers will suffice, use a heuristics algorithm.
- Algorithm guaranteed to be no larger than twice the size of the optimal vertex cover
- If exact answers are a requirement, design an algorithm that’s exponential yet better than brute-force
- Fuzz testing algorithms
- Personnel scheduling (find the smallest set of people whom have a particular set of skills)
- Placing enough guards to cover an area
- Wireless telecommunication
- Circuit design
Click here for build and run instructions