**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 \(\{D, C\}\) 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
- Small vertex cover - When the vertex cover is small ($\approx \leq \log n$) the runtime is tractable. $O(2^k m)$ where $k$ is the size of the vertex cover
- Tree Graphs - Using a dynamic programming algorithm.
- Bipartite Graphs - Using an application of the maximum flow problem.

- 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

## Applications

- 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

## Asymptotic Complexity

Under Construction

## Pseudo Code

Under Construction

## Source Code

Relevant Files:

Under Construction

Click here for build and run instructions