Let $B$ be an undirected tree with $|V|$ nodes given as adjacency list. I want to develop a greedy algorithm using pseudo code to find a maximal matching in runtime $\mathcal{O}(|V|)$.

My approach:

Find all leaves. For each leaf if the parent edge has not been seen by another leaf, mark the edge to its parent as matching edge. Now delete all found leaves, its parents and the associated edges of the parents. Start over from the beginning.

Pseudo code:

graph = {
     1: [2, 3],
     2: [1, 4, 5],
     3: [1, 6],
     4: [2, 7, 8],
     5: [2, 9],
     6: [3],
     7: [4, 10, 11],
     8: [4, 12, 13],
     9: [5],
    10: [7, 14],
    11: [7],
    12: [8],
    13: [8, 15, 16],
    14: [10],
    15: [13],
    16: [13],
# example graph I used for testing purposes

while we haven't seen all nodes:
    leaves = [i for i in graph if len(graph[i]) == 1]
    seen += leaves
    for leaf in leaves:
        parent = graph[leaf][0]
        del graph[leaf]  # Throw away all leaves
        if not parent in seen:
            del graph[parent] # And throw away their parent
            matching_edges += [(leaf, parent)]
            seen += [parent]
            next_round_nodes += [parent]

But I'm afraid that is not linear, is it? Because first we look at $|V|$ and perform our algo. Then we do the same with $|V|-c$ leaves, where $c$ could actually be 2, if I understand that correctly, looking at graph which is a "line". So, really that seems quadratic.


  1. Is my algorithm correct?
  2. What is the runtime?
  3. If it is not linear, what other approach could I chose?

It is correct and runs in linear time. You can run a DFS to find the height and the parent node of each vertex and visit the vertices according to their heights in ascending order.

The correctness of such algortihms is usually proved using an exchange argument. Assume $M$ is the matching computed by your algortihm and $M_{\mathrm{OPT}}$ an arbitrary maximum matching. Show that you can turn $M_{\mathrm{OPT}}$ into $M$ by removing and adding edges to the matching where its size never gos smaller.

  • 1
    $\begingroup$ Thanks for the response! Could elaborate on the correctness proof? Could I show it with induction as well? It's pretty straight forward to that I think. For every iteration the resulting graph is of the same structure, just a little smaller. $\endgroup$ – Marcel B Nov 19 at 16:49
  • $\begingroup$ Yes actually induction might be simpler here, over the height of the tree. Try to do it as an exercise. I would be glad to help if you get stuck. $\endgroup$ – narek Bojikian Nov 19 at 16:53
  • $\begingroup$ Hint: Actually induction would make the exchange argument simpler (also on the other way) assume that you can turn the opt solution to yours in all subtrees rooted at direct children of the root and show that you can then turn the optimal in the whole tree into your soltion $\endgroup$ – narek Bojikian Nov 19 at 16:56

Your Answer

