1
$\begingroup$

This question deals with how to find the maximum matching in a tree. I understood the answers, but for one part.

Choose a root arbitrarily. For each subtree, calculate the maximum matching within the subtree, as well the maximum matching within the subtree that doesn't touch the root of the subtree. You can think of it as a form of dynamic programming.

How do we prove that choosing a root arbitrarily does not result in a non-optimal solution?

I tried to think in terms of another solution: every tree is a bipartite graph, and size of maximum matching in a bipartite graph equals maximum flow in a modified graph. But could not proceed.


Edit:

Let the nodes of the rooted tree be $1,\dots,n$.

I am using these DP states

  • $without[i]$ is the size of a maximum matching in the subtree of node $i$, where $i$ is not matched to any of its children
  • $with[i]$ is the size of a maximum matching in the subtree of node $i$, where $i$ is matched to one of its children

Transitions

  • $without[i] = \sum_{j\in children(i)}\big[\max(with[j],without[j])\big]$
  • $with[i] = \sum_{j\in children(i)}\bigg[1+without[j]+\sum_{k\in children(i)\backslash j}\big[\max(with[k],without[k])\big]\bigg] \\ = \sum_{j\in children(i)}\big[1+without[j]+(without[i]-\max(with[j],without[j]))\big]$
$\endgroup$

1 Answer 1

0
$\begingroup$

You can prove this by a case analysis. Consider any optimal solution. Either the root is matched to another vertex, or it is unmatched. If it is matched to some other vertex, consider all possible cases for what the root might be matched to. Make sure that your dynamic programming algorithm handles all of those cases correctly.

In other words, the way you prove it is correct is by writing down a proof of correctness for your algorithm (which happens to choose the root arbitrarily). I have attempted to outline above how I anticipate such a proof of correctness will go. If the proof works correctly no matter how the root is chosen, then you have solved your problem.

$\endgroup$
2
  • $\begingroup$ I'm not sure if I understand. I have edited the question to include my DP approach $\endgroup$
    – muser
    Dec 20, 2022 at 6:19
  • $\begingroup$ @abs, I have edited my answer. $\endgroup$
    – D.W.
    Dec 20, 2022 at 6:21

Your Answer

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

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