Vertex Cover

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:

Vertex Cover

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
    • 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

Full Repo

Relevant Files:
Under Construction

Click here for build and run instructions