Minimum Vertex Cover Problem

graph-theory computation

Definition

Minimum Vertex Cover Problem

The minimum vertex cover problem is a minimisation problem that asks for a vertex cover of minimum cardinality.

Instance: undirected graph $G=(V,E)$

Task: Find a set $S\subseteq V$ such that every edge in $E$ has at least one endpoint in $S$, and $|S|$ is minimum.

Greedy by degree

Highest-degree first

Choose a vertex of maximum degree, add it to the solution, and delete all edges incident to it. Repeat until no edge remains.

The output is always a vertex cover, because the algorithm stops only when every edge has been deleted.

Highest-degree first is a natural greedy algorithm, but it is not a constant-factor approximation in general. Its solution can be logarithmically larger than an optimum solution.

Bad tie-breaking

Consider the path graph on five vertices. The vertices $v_2$, $v_3$, and $v_4$ all have maximum degree $2$.

If highest-degree first chooses $v_3$ first, then the remaining uncovered edges are $\{v_1,v_2\}$ and $\{v_4,v_5\}$. The algorithm must then choose one endpoint of each remaining edge. One possible output is

$$S_{\mathrm{HDF}}=\{v_2,v_3,v_4\}.$$

But an optimum vertex cover is

$$S^{\ast }=\{v_2,v_4\}.$$

HDF guarantee

Let $S_{\mathrm{HDF}}$ be the vertex cover returned by highest-degree first. Then

$$|S_{\mathrm{HDF}}|\le (\ln |E|+1)\cdot |S^{\ast }|,$$

where $S^{\ast }$ is a minimum vertex cover.

$k=|S^{\ast }|$. Let $E_i$ be the set of remaining edges after $i$ iterations, and write $m_i=|E_i|$.

Since $E_i\subseteq E$, the set $S^{\ast }$ still covers every edge in $E_i$. Thus, the $k$ vertices in $S^{\ast }$ cover $m_i$ edges. Hence at least one vertex in $S^{\ast }$ is incident to at least

$$\frac{m_i}{k}$$

edges of $E_i$.

Highest-degree first chooses a vertex of maximum degree, so it deletes at least $m_i/k$ edges. Therefore,

$$m_{i+1}\le m_i-\frac{m_i}{k}=\left(1-\frac{1}{k}\right)m_i.$$

Repeating this inequality gives

$$m_i\le {\left(1-\frac{1}{k}\right)}^i|E|\le e^{-i/k}|E|.$$

For $i>k\ln |E|$, this gives $m_i<1$. Since $m_i$ is an integer, $m_i=0$. Thus, the algorithm terminates after at most $\lceil k\ln |E|\rceil +1$ iterations.

Therefore,

$$|S_{\mathrm{HDF}}|\le \lceil k\ln |E|\rceil +1\le (\ln |E|+1)k.$$

Greedy by matching

Maximal matching

Find a maximal matching $M$ of $G$ and return all matched vertices:

$$V_M=\{u,v\mid \{u,v\}\in M\}.$$

This algorithm is simpler to analyse than highest-degree first. The matching gives a lower bound on the optimum, and taking both endpoints gives a feasible cover.

Maximal matching approximation

The maximal matching algorithm returns a vertex cover $V_M$ with

$$|V_M|\le 2|S^{\ast }|,$$

where $S^{\ast }$ is a minimum vertex cover.

$V_M$ is a vertex cover. If some edge $e\notin M$ had no endpoint in $V_M$, then $e$ could be added to $M$. This would contradict maximality of $M$.

Second, every vertex cover must cover every edge in $M$. Since edges in a matching are pairwise disjoint, covering all edges of $M$ requires at least one distinct vertex per matched edge. Hence

$$|M|\le |S^{\ast }|.$$

The algorithm returns both endpoints of each edge in $M$, so

$$|V_M|=2|M|\le 2|S^{\ast }|.$$

Complexity

The decision version of the problem is NP-complete. The optimisation problem is NP-hard.

Approximation boundary

The maximal matching algorithm gives a simple $2$-approximation.

It is a long-standing open problem whether minimum vertex cover has a polynomial-time approximation algorithm with factor strictly smaller than $2$.