The Edge-Selection Algorithm
A vertex cover must meet every edge, but finding a smallest such set can be difficult. A simple algorithm builds a cover by repeatedly choosing an edge that is not yet covered and adding both of its endpoints. Its output can contain more vertices than necessary. The key to bounding how many more is to remember the edges chosen along the way: no two of them share a vertex, so each one forces any vertex cover to include at least one distinct vertex.
Throughout, \(G=(V,E)\) is a finite simple graph. A set \(C\subseteq V\) is a vertex cover if every edge has at least one endpoint in \(C\). The vertex cover number \(\tau(G)\) is the minimum size of a vertex cover. This minimum exists: \(V\) is a vertex cover, and there are finitely many subsets of \(V\). A matching is a set of edges no two of which share an endpoint.
The set \(M\) records the chosen edges; it is not itself the returned vertex cover. A matching is maximal if no edge can be added to it while keeping it a matching. It is maximum if it has the largest size among all matchings in the graph. These are different properties: maximality means no single edge can be added, whereas maximum size compares against every matching. The algorithm's \(M\) is maximal, but need not be maximum.
Why the Matching Gives a Lower Bound
Proof. Let the matching edges be \(e_1,\dots,e_k\), and let \(C\) be any vertex cover. Because \(C\) covers each \(e_i\), it contains at least one endpoint of each edge. Since the matching edges are pairwise vertex-disjoint, endpoints chosen from different edges must be different vertices. Thus \(C\) contains at least \(k\) vertices, so \(|C|\ge k\). This applies to a minimum cover as well, giving \(\tau(G)\ge k\). If \(k=0\), the conclusion is simply \(|C|\ge0\), which also holds. \(\square\)
The important feature is that the lower bound applies to every matching, not just a maximum one. The algorithm needs only the matching that it constructs itself. It does not need to solve the separate problem of finding a largest matching.
The Two-Approximation Guarantee
Proof. Each time the algorithm selects \(uv\), both endpoints are added to \(C\). Therefore every later edge incident to \(u\) or \(v\) is already covered. No later selected edge can share an endpoint with \(uv\), so the selected edges in \(M\) form a matching. Write \(k=|M|\). Each selected edge adds exactly two previously unselected vertices: before its selection, both endpoints are outside \(C\), and all endpoints added in earlier steps stay in \(C\). Consequently, \(|C|=2k\).
When the algorithm stops, there is no edge with both endpoints outside \(C\). This is exactly the condition that every edge has an endpoint in \(C\), so \(C\) is a vertex cover. The matching lower bound gives \(k\le\tau(G)\). Hence $$ |C|=2k\le2\tau(G). $$ If \(E=\varnothing\), the loop makes zero selections, so \(k=0\), \(C=\varnothing\), and \(\tau(G)=0\). The same inequality then reads \(0\le0\); a ratio with denominator \(\tau(G)=0\) is not needed. At termination every edge meets an endpoint of a selected edge, so no additional edge can be added to \(M\) while preserving a matching. Thus \(M\) is maximal, though it need not be maximum. \(\square\)
One implementation scans the edge list once. For each edge, select it if neither endpoint has yet been added to \(C\); otherwise skip it. An edge skipped this way already has an endpoint in \(C\), and later steps never remove vertices, so it remains covered. This scan produces the same kind of valid output and takes \(O(|V|+|E|)\) time with an edge list and a membership mark for each vertex. Its approximation guarantee holds for every ordering of the edges.
Worked Examples
Worked Example: A Tight Factor of Two
Let \(V=\{1,2,3,4,5,6\}\) and \(E=\{12,34,56\}\). Process the edges in the order shown.
| Step | Edge considered | Action | \(C\) afterward | \(M\) afterward |
|---|---|---|---|---|
| Start | — | Initialize | \(\varnothing\) | \(\varnothing\) |
| 1 | \(12\) | Select; add 1 and 2 | \(\{1,2\}\) | \(\{12\}\) |
| 2 | \(34\) | Select; add 3 and 4 | \(\{1,2,3,4\}\) | \(\{12,34\}\) |
| 3 | \(56\) | Select; add 5 and 6 | \(\{1,2,3,4,5,6\}\) | \(\{12,34,56\}\) |
The output has size \(2\cdot3=6\), and it covers all three edges. To calculate the optimum, each of the three disjoint edges requires a vertex, so every cover has size at least \(3\). The set \(\{1,3,5\}\) covers all three edges and has size \(3\); therefore \(\tau(G)=3\). The ratio is \(6/3=2\), so the factor-two bound can be attained.
Check: the selected edges are pairwise disjoint and number \(3\), giving the lower bound \(\tau(G)\ge3\). The exhibited cover has size \(3\), confirming \(\tau(G)=3\). The algorithm's output has size \(6=2\tau(G)\).
Worked Example: A Cover Smaller Than the Bound
Let \(V=\{1,2,3,4,5,6\}\) and \(E=\{12,23,13,45\}\). Vertex \(6\) is isolated. Process \(12\), then \(45\), then the remaining triangle edges.
| Step | Edge considered | Action | \(C\) afterward | \(M\) afterward |
|---|---|---|---|---|
| Start | — | Initialize | \(\varnothing\) | \(\varnothing\) |
| 1 | \(12\) | Select; add 1 and 2 | \(\{1,2\}\) | \(\{12\}\) |
| 2 | \(45\) | Select; add 4 and 5 | \(\{1,2,4,5\}\) | \(\{12,45\}\) |
| 3 | \(23\) | Skip; 2 is already in \(C\) | \(\{1,2,4,5\}\) | \(\{12,45\}\) |
| 4 | \(13\) | Skip; 1 is already in \(C\) | \(\{1,2,4,5\}\) | \(\{12,45\}\) |
The output covers \(12\), \(23\), \(13\), and \(45\), and it does not need the isolated vertex \(6\). To find the optimum, any cover must include at least two vertices from \(\{1,2,3\}\): choosing only one leaves the edge between the other two uncovered. It must also include at least one of \(4,5\), since otherwise \(45\) is uncovered. These requirements concern disjoint vertex sets, so every cover has size at least \(2+1=3\). The set \(\{1,2,4\}\) covers all four edges, so \(\tau(G)=3\). The returned cover has size \(4\), and its ratio is \(4/3\).
Check: the matching \(M=\{12,45\}\) has size \(2\), so the matching lower bound gives \(\tau(G)\ge2\), not \(\tau(G)=2\). The direct argument and the cover \(\{1,2,4\}\) establish \(\tau(G)=3\). The algorithm's bound checks numerically as \(4\le2\cdot3=6\).
Worked Example: Edge Order Can Change the Output
Let \(V=\{1,2,3,4\}\) and \(E=\{12,23,34\}\), the path on four vertices. First process the edges in the order \(12,23,34\).
| Step | Edge considered | Action | \(C\) afterward | \(M\) afterward |
|---|---|---|---|---|
| Start | — | Initialize | \(\varnothing\) | \(\varnothing\) |
| 1 | \(12\) | Select | \(\{1,2\}\) | \(\{12\}\) |
| 2 | \(23\) | Skip; 2 is covered | \(\{1,2\}\) | \(\{12\}\) |
| 3 | \(34\) | Select | \(\{1,2,3,4\}\) | \(\{12,34\}\) |
This run returns a cover of size \(4\). Now process \(23\) first. The algorithm selects it and adds 2 and 3. The edge \(12\) is then covered by 2, and \(34\) is covered by 3, so the run stops with \(C=\{2,3\}\) and \(M=\{23\}\). Both outputs are covers. The set \(\{2,3\}\) is optimal because it covers all three edges, while any cover needs at least two vertices: one vertex cannot meet both disjoint edges \(12\) and \(34\). Thus \(\tau(G)=2\). The first run has ratio \(4/2=2\), and the second has ratio \(2/2=1\).
Check: for the first ordering, \(M=\{12,34\}\) has size \(2\); for the second, \(M=\{23\}\) has size \(1\). The second matching is maximal, since each other edge meets \(23\), but it is not maximum: \(\{12,34\}\) is a matching of size \(2\). In both runs, the output size is twice the number of selected edges.
What the Guarantee Does—and Does Not—Say
The proof uses two separate facts: the output has exactly two endpoints for each selected edge, and each selected edge forces an optimal cover to use at least one vertex. Together these give \(|C|=2|M|\le2\tau(G)\). The proof does not claim that the algorithm finds a minimum cover, or that its selected matching has maximum size. The path example shows that choosing a different uncovered edge can change both the matching and the returned cover.
A common mistake is to treat the matching lower bound as an equality. In the triangle with edges \(\{12,23,13\}\), if the algorithm selects \(12\), then \(|M|=1\). The valid conclusion is \(\tau(G)\ge1\), not \(\tau(G)=1\). The proposed one-vertex cover \(\{1\}\) misses edge \(23\). In fact, at least two vertices are needed to cover all three triangle edges, and any two do cover them, so \(\tau(G)=2\). A matching certifies a lower bound; by itself, it need not identify the optimum.
The algorithm is useful because it is easy to implement and its guarantee holds regardless of how uncovered edges are chosen. It also illustrates a general proof strategy for approximation algorithms: construct a feasible solution, find a lower bound on the optimum, and compare the constructed solution's size with that bound. Here feasibility comes from stopping only when every edge is covered, and the lower bound comes from disjointness of the selected edges.
Check Your Understanding
For each question, distinguish the algorithm's selected matching from its returned vertex cover.
- Run the algorithm on \(V=\{1,2,3,4\}\), \(E=\{12,23,34\}\), choosing \(23\) first. What are \(M\) and \(C\), and what is \(\tau(G)\)?
- Why can no two selected edges share an endpoint?
- If an execution selects \(k\) edges, what lower bound does this give on \(\tau(G)\), and why?
- Give a graph and an edge order for which the algorithm returns a cover of size exactly twice the optimum.
- What does the algorithm return when \(E=\varnothing\), and how does the guarantee apply in that case?