Minimal Vertex Cover Problem

computation

Definition

Minimal Vertex Cover Problem

The minimal vertex cover problem is an NP-complete minimisation problem that tries to find the vertex cover of a graph with the smallest possible number of vertices.

Approaches

Branch and Bound

A branch and bound approach for the MVC problem can be done by sorting (descending) the vertices by their degree. Choose the first vertex $v_0$, two sub-problems emerge:

1. $v_0$ is included in the solution
2. $N(v_0)$, $v_0$‘s neighbours, are included in the solution (apply 1. for every $v_1\in N(v_0)$)

The lower and upper bound constraint the number of vertices that are required to form a minimal vertex cover.