It's a question from a previous exam that I'm trying to solve with no success.
Suggest a Dynamic-Programming algorithm for the following problem:
Input: indirected tree $T(V, E)$.
Output: a Maximum-Matching in the tree.
Any node have additional $O(1)$ memory.
Required Big-O: $O(|V|)$.
I don't have a clue how to start.
Can you kindly give me some hints to solve it?
Thanks in advance.
Best Answer
One thing that helps is to root the tree, simply by assigning an arbitrary vertex $r$ as the root of $T$.
In this case, dynamic programming on trees often work in a bottom-up manner (or post-order traversal of the vertices).
That is, say you have a function $f : V \rightarrow \mathbb{N}$ where $f(v)$ is the score of the maximum matching of the subtree rooted at $v$. The function $f(v)$ relies on the values of $f(v_1), f(v_2), \ldots, f(v_k)$, where $v_1, \ldots, v_k$ are the children of $v$ in $T$. When you work up your way to $f(r)$, you are done.
In the problem of max matching, there are two cases for a given $v$. Either you include exactly one edge joining $v$ and one of its children, or you include no such edge.
So actually you might need to pieces of information for each $v$. Call $g(v, 0)$ the score of a max matching of the tree rooted at $v$ that includes no edge between $v$ and one of its children. And call $g(v, 1)$ the score when $v$ includes one such edge.
Now, given $g(v_i, 0)$ and $g(v_i, 1)$ for every child $v_i$ of $v$, can you compute $g(v, 0)$ and $g(v, 1)$. Can you compute $f(v)$ from that ?