Maximal Matching Minimum Vertex Cover Algorithm

Definition

Maximal Matching Minimum Vertex Cover Algorithm

Let 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 , , and , choose any edge and set

Here, deletes both endpoints and every edge incident to either endpoint. The algorithm stops when no edge remains and returns . The selected edge set is then a maximal matching.

Two-Approximation

Two-Approximation Bound

The maximal matching algorithm is a two-approximation: if is its returned vertex cover and is a minimum vertex cover, then

Proof

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

The selected edges form a matching

After selecting , the algorithm deletes , , and every incident edge. No later selected edge can therefore share an endpoint with :

Hence 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 , so is maximal.

The output covers every edge

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

Thus is a vertex cover.

Every matching edge meets the minimum cover

Since and is a vertex cover,

The injective endpoint selection therefore gives a function

Compare the two covers

An injection assigns a different vertex of to every edge of . By the pigeonhole principle, such an injection can exist only if is no larger than :

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

Examples

Choosing first

Consider the path graph

First choose the edge . Both endpoints enter the cover, and the incident edges , , and are deleted:

Next choose . This adds and and deletes both remaining edges:

The selected edges form the matching

because every unselected edge intersects an edge in :

Hence no edge can be added to while preserving the matching property, so is maximal. It is not maximum: the matching has three edges.

The algorithm returns the vertex cover . It is not minimum: for example, is a vertex cover with .