Maximal Matching Minimum Vertex Cover Algorithm

Definition

Maximal Matching Minimum Vertex Cover Algorithm

Let $G=(V,E)$ be a finite undirected graph. The maximal matching algorithm is a greedy minimum vertex cover algorithm for the minimum vertex cover problem. It repeatedly chooses an arbitrary remaining edge and adds both endpoints to the cover.

Starting with $G_0=G$, $C_0=\varnothing$, and $M_0=\varnothing$, choose any edge $e_i=\{u_i,v_i\}\in E(G_i)$ and set

$$\begin{array}{rl}{C}_{i+1}& =C_i\cup \{u_i,v_i\},\\ M_{i+1}& =M_i\cup \{e_i\},\\ G_{i+1}& =G_i-\{u_i,v_i\}.\end{array}$$

Here, $G_i-\{u_i,v_i\}$ deletes both endpoints and every edge incident to either endpoint. The algorithm stops when no edge remains and returns $C_i$. The selected edge set $M_i$ is then a maximal matching.

Two-Approximation

Two-Approximation Bound

The maximal matching algorithm is a two-approximation: if $C$ is its returned vertex cover and $S^{\ast }$ is a minimum vertex cover, then

$$|C|\le 2|S^{\ast }|.$$

Proof

Let $M$ be the set of edges selected by the algorithm, and let $t$ be the number of iterations before it terminates.

The selected edges form a matching

After selecting $e_i=\{u_i,v_i\}$, the algorithm deletes $u_i$, $v_i$, and every incident edge. No later selected edge can therefore share an endpoint with $e_i$:

$$i<j⟹\underset{\text{disjoint endpoints}}{\underbrace{e_i\cap e_j=\varnothing }}.$$

Hence $M$ is a matching. Every unselected edge is eventually deleted because it shares an endpoint with a selected edge. No original edge can therefore be added to $M$, so $M$ is maximal.

The output covers every edge

An edge disappears only when one of its endpoints is added to $C$. Therefore,

$$\underset{\text{no edge remains}}{\underbrace{E(G_t)=\varnothing }}⟹\underset{\text{every edge is covered}}{\underbrace{\forall e\in E:e\cap C\ne \varnothing }}.$$

Thus $C$ is a vertex cover.

Every matching edge meets the minimum cover

Since $M\subseteq E$ and $S^{\ast }$ is a vertex cover,

$$\forall e\in M:e\cap S^{\ast }\ne \varnothing ⟺\forall \{a,b\}\in M:a\in S^{\ast }\vee b\in S^{\ast }.$$

The injective endpoint selection therefore gives a function

$$f:M\hookrightarrow S^{\ast },f(e)\in e\cap S^{\ast }.$$

Compare the two covers

An injection $f:M\to S^{\ast }$ assigns a different vertex of $S^{\ast }$ to every edge of $M$. By the pigeonhole principle, such an injection can exist only if $M$ is no larger than $S^{\ast }$:

$$\underset{\text{one distinct cover vertex per edge}}{\underbrace{f:M\hookrightarrow S^{\ast }}}⟹|M|\le |S^{\ast }|.$$

The algorithm adds both endpoints of every edge in $M$. Because matching edges are disjoint and each edge has two endpoints,

$$\begin{array}{rl}\underset{\text{chosen endpoints}}{\underbrace{|C|}}& =\sum _{e\in M}|e|\\ & =\sum _{e\in M}2\\ & =2|M|\le 2|S^{\ast }|.\end{array}$$

Examples

Choosing $\{B,C\}$ first

Consider the path graph

$$A-B-C-D-E-F.$$

First choose the edge $e_0=\{B,C\}$. Both endpoints enter the cover, and the incident edges $\{A,B\}$, $\{B,C\}$, and $\{C,D\}$ are deleted:

$$\begin{array}{rl}{C}_1& =\{B,C\},\\ E(G_1)& =\{\{D,E\},\{E,F\}\}.\end{array}$$

Next choose $e_1=\{E,F\}$. This adds $E$ and $F$ and deletes both remaining edges:

$$\begin{array}{rl}{C}_2& =\{B,C,E,F\},\\ E(G_2)& =\varnothing .\end{array}$$

The selected edges form the matching

$$M=\{\{B,C\},\{E,F\}\},$$

because every unselected edge intersects an edge in $M$:

$$\begin{array}{rl}\{A,B\}\cap \{B,C\}& =\{B\},\\ \{C,D\}\cap \{B,C\}& =\{C\},\\ \{D,E\}\cap \{E,F\}& =\{E\}.\end{array}$$

Hence no edge can be added to $M$ while preserving the matching property, so $M$ is maximal. It is not maximum: the matching $\{\{A,B\},\{C,D\},\{E,F\}\}$ has three edges.

The algorithm returns the vertex cover $C_2=\{B,C,E,F\}$. It is not minimum: for example, $S^{\ast }=\{B,D,F\}$ is a vertex cover with $|S^{\ast }|=3<4=|C_2|$.