Greedy Algorithms on Trees

A vertex cover touches every edge with at least one selected endpoint. On an unweighted tree, a remaining leaf gives a safe greedy choice: select its only remaining neighbor. Removing that neighbor’s incident edges leaves a forest, so the argument repeats. This yields a linear-time minimum cover without a full DP table, while exposing exactly why tree structure and equal vertex costs matter.

Prerequisites: Tree Representation; queues; Tree Dynamic Programming. Related existing lessons: Tree Dynamic Programming.

Build the idea

1. Use the remaining forest, not original degrees

   Read a valid connected tree with vertices 1…n and n−1 edges. degree tracks edges whose endpoints remain active, not the original degree. Put current degree-one vertices into a queue. Isolated vertices need no cover choice. alive marks which vertices still participate; selected neighbors are removed along with all incident edges.

2. Process a leaf safely

   Pop leaf L and ignore stale entries whose vertex is gone or degree is no longer one. Find its active neighbor P, select P and remove it. Decrement the degrees of active neighbors of P and enqueue any newly exposed leaves. The selected vertex can cover several leaf edges at once; choosing every leaf instead would often be wasteful.

   $$\mathrm{minCover}\left(\mathrm{forest}\right)=1+\mathrm{minCover}\left(\mathrm{forest}\mathrm{after}\mathrm{selecting}P\right)$$

3. Correctness proof: exchange and residual optimum

   Every cover must contain L or P to cover their edge. If an optimal cover contains L but not P, replace L by P: L has no other remaining edge, while P covers that edge and possibly more, without increasing cardinality. Thus some optimum contains P. Fix P and delete its covered edges; an optimal cover of the remaining forest plus P is optimal for the original residual instance. Induct until no edges remain. Every nonempty tree component has a leaf, so the queue process cannot leave an unhandled edge.

4. Trace a path

   For edges 1–2–3–4–5, initial leaves are 1 and 5. Processing 1 selects 2, removing edges 1–2 and 2–3. Processing 5 selects 4, removing 3–4 and 4–5. Remaining isolated vertices need no selection. Output {2,4} covers all four edges; the exchange proof establishes that two is minimum, not merely that this cover is valid.

5. Compare general graphs and DP

   A triangle has no leaves but still needs a cover of size two; running only this leaf loop on an arbitrary graph would miss its edges. Weighted costs also break the equal-cardinality exchange: a costly star center may be worse than its cheap leaves. Tree DP with states “take vertex” and “skip vertex” handles weights and reconstructs choices. The unweighted cover size also equals n minus the maximum independent-set size, linking to the existing Tree DP lesson.

This is a complete program. Compile with C++17 and enter the input described below.

#include<iostream>
#include<vector>
#include<queue>
#include<algorithm>
int main(){
    int n;
    std::cin>>n;
    std::vector<std::vector<int>>tree(n+1);
    std::vector<int>degree(n+1);
    for(int i=1;i<n;++i){
        int u,v;
        std::cin>>u>>v;
        tree[u].push_back(v);
        tree[v].push_back(u);
        ++degree[u];
        ++degree[v];
    }
    std::queue<int>leaves;
    for(int u=1;u<=n;++u){
        if(degree[u]==1){
            leaves.push(u);
        }
    }
    std::vector<bool>alive(n+1,true);
    std::vector<int>cover;
    while(!leaves.empty()){
        int leaf=leaves.front();
        leaves.pop();
        if(!alive[leaf]||degree[leaf]!=1){
            continue;
        }
        int parent=0;
        for(int v:tree[leaf]){
            if(alive[v]){
                parent=v;
                break;
            }
        }
        cover.push_back(parent);
        alive[parent]=false; // Choosing the leaf's only neighbor safely covers all its incident edges.
        for(int v:tree[parent]){
            if(alive[v]){
                --degree[v];
                if(degree[v]==1){
                    leaves.push(v);
                }
            }
        }
    }
    std::vector<bool>selected(n+1,false);
    for(int u:cover){
        selected[u]=true;
    }
    cover.clear();
    for(int u=1;u<=n;++u){
        if(selected[u]){
            cover.push_back(u);
        }
    }
    std::cout<<cover.size()<<'\n';
    for(int i=0;i<(int)cover.size();++i){
        std::cout<<cover[i]<<(i+1==(int)cover.size()?'\n':' ');
    }
    if(cover.empty()){
        std::cout<<'\n';
    }
}

Complexity analysis

O(n) time and O(n) adjacency/degree/queue storage. Each vertex is removed at most once and original adjacency lists are scanned only a constant number of times. Output is ordered by a boolean-ID scan rather than an extra O(n log n) sort. Iterative processing avoids deep DFS recursion.

Example input and output

Read n (1..200000), then n−1 edges of a valid connected tree, vertices 1..n. All vertex costs are one. Print minimum cover size and selected IDs in increasing order. A singleton needs the empty cover.

Input

5
1 2
2 3
3 4
4 5

Output

2
2 4

Selecting the two parents of the path’s end leaves covers all edges; the middle vertex becomes isolated.

Practical applications

Use leaf-based exchanges on unweighted forests when a forced edge can be covered by replacing a leaf with its neighbor. Prefer tree DP for weighted or richer states and use the existing Trees folder for those prerequisites. General vertex cover is not solved by this routine.

Check your understanding

Why can an optimal unweighted cover select the parent instead of its leaf?

Put it into practice

Compare all vertex subsets on random trees with at most eleven vertices.