0
$\begingroup$

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 O(|V|).

I understand that the solution is:
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.

Like that described here: How to find maximum matching edges in undirected tree

But I did not understand how this can be proved by induction on the height of the tree. Can you help with this?

Improve this question
$\endgroup$
2
  • $\begingroup$ While the algorithm mentioned in that post can be implemented in $O(|V|)$ time. However, the mentioned code has $\Theta(n^2)$ complexity in the worst case. For example consider the path graph. Since the code is finds a leaf in $O(n)$ time at every iteration, overall time is $O(n^2)$ for a path graph. $\endgroup$
    – Inuyasha Yagami
    Jan 28, 2022 at 15:35
  • $\begingroup$ Please describe the implementation of the algorithm in your way (pseudocode) that you have understood. Then, we can discuss about its running time complexity and correctness. Please edit your post accordingly. $\endgroup$
    – Inuyasha Yagami
    Jan 28, 2022 at 15:38

1 Answer 1

Reset to default
2
$\begingroup$

You don't have to prove it using induction, although you can. You can prove the following for general graphs.

Observation 1. If a vertex has degree 1, there is a maximum matching containing that vertex.

Proof. By an exchange argument, let M be maximum, not containing the vertex. Why? Because it's neighbor is matched to a different vertex. Create a new maximum matching containing the degree 1 vertex instead.

Observation 2. If an edge is chosen to be in the matching, we can delete the endpoints of the edge and continue with the smaller graph instance.

Proof. You can probably take it.

Observation 3. If a vertex has degree 0, you can delete it from the graph and continue with the smaller graph instance.

Now the correctness of the algorithm is immediate on forests, since any forest with an edge has a vertex with degree 1.

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.