PvPro's blog

Perfect matching in tree
By PvPro, history, 3 weeks ago, translation, In English

Hello codeforces!

What is the easiest way to check if there is a perfect matching in the tree?

Maybe Kuhn's algorithm? :)

Most likely you are thinking about dynamics on subtrees. This is indeed a good way, because it works for the size of the input. However, there is an easier way to check if a tree has a perfect matching.

Let $$$sz_v$$$ be the subtree size of the $$$v$$$th vertex. Then I claim that there is a perfect matching iff exactly half of all $$$sz_v$$$ are even.

Proof:

Let $$$sz_{odd}$$$ be the number of odd subtrees, and $$$sz_{even}$$$ be the number of even subtrees.

We first prove that $$$sz_{even} \leq sz_{odd}$$$.

Note that $$$sz_v = \sum_{u}^{} sz_u + 1$$$ ($$$u$$$ — child of $$$v$$$). If $$$sz_v$$$ is even, then at least one of the children of $$$u$$$ has an odd subtree size, because their sum is odd. We pair each even $$$sz_v$$$ with an odd $$$sz_u$$$ ($$$u$$$ — child $$$v$$$). Thus $$$sz_{even} \leq sz_{odd}$$$. Moreover, we proved that if $$$sz_{even} = sz_{odd}$$$, then there is a perfect matchingg in the tree by explicitly choosing every even $$$sz_v$$$ to be a pair.

Now we prove that if $$$sz_{even} \neq sz_{odd}$$$, then there is no perfect matching in the tree. Suppose there is. Then it has an edge connecting $$$v, u$$$ such that $$$sz_v \equiv sz_u \equiv 1\space (mod\space 2)$$$. Let $$$v$$$ — be the parent of $$$u$$$. Then note that each edge is either entirely contained in a subtree of $$$v$$$ or not. In both cases, the edge takes an even number of vertices from subtree $$$v$$$, and hence they will also take an even number of vertices in total, but $$$sz_v \equiv 1\space(mod\space 2)$$$ — contradiction.

Furthermore, because of the inequality $$$sz_{even} \leq sz_{odd}$$$ it is true that $$$sz_{odd} = sz_{even}$$$ is equivalent to the presence of a perfect matching in the forest.

Thanks for reading!

  • Vote: I like it
  • +185
  • Vote: I do not like it

»
3 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

Auto comment: topic has been translated by PvPro (original revision, translated revision, compare)

→ Reply
»
3 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

Auto comment: topic has been updated by PvPro (previous revision, new revision, compare).

→ Reply
»
3 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

Very nice idea. I have attempted to repackage the ideas of the proof into a more colloquial explanation. Note I will use “odd/even vertex” to mean a vertex with an odd/even sized subtree.


There are two key observations: every odd vertex must be matched with its parent, and every even vertex has at least one odd child. So to construct a perfect matching, we must match every even vertex to one of its odd children. If |{odd vertices}| = |{even vertices}|, we have found a perfect matching. Else the matching cannot be completed as the only unmatched vertices are odd, and odd vertices cannot be matched to each other because every odd vertex must be matched with its parent.

→ Reply
»
3 weeks ago, # |
← Rev. 2   Vote: I like it +50 Vote: I do not like it

I have seen and self derived a generalisation of this lemma a few times. Details:

Lemma: Let k be an integer and G be a tree of size n. Suppose n is divisible by k, then we can split G into exactly (n/k) connected components of equal size, iff there are (n/k) subtree sizes that are divisble k.

Proposition: The number of subtree sizes are always $$$\leq n/k$$$.

Proof of lemma: If we just make cuts from every such subtree, then every commponent would have size multiple of $$$k$$$. But we have $$$n/k$$$ such components and they are not empty, so each of them must be size $$$k$$$.

Conversely, the subtree of LCA of any given component must always be written as a disjoint unions of components. THese give (n/k) vertices whose subtrees sizes divisible by $$$k$$$.

Proof of Proposition: For a direct proof: Use strong induction on the following statement instead: The number of such subtree are at most $$$\leq n/k$$$, but we do not require $$$n$$$ to be divisble by $$$k$$$. Alternatively, through the proof of previous lemma, we gets more than n/k nonempty components, each of size divisble by $$$k$$$. This is a contradiction.

Edit: thanks for pointing out missing defintion of k

→ Reply
  • »
    »
    3 weeks ago, # ^ |
      Vote: I like it +23 Vote: I do not like it

    This generalization (I assume that k is the target size of each of the connected component) is the statement of 2011 Polish ICPC (AMPPZ) problem "Jaskinia" ("Cave"). The only difference is that in this problem, for a given tree you must identify all n/ks that will work (and output them in an increasing order).

    → Reply
»
3 weeks ago, # |
← Rev. 2   Vote: I like it +35 Vote: I do not like it

Also, worth mentioning that following simple greedy is both useful and instructive. It should not be overlooked:

Process all leafs one by one, commit to match it with its parents. If the parent was already matched, that this leaf will be discraded.

This also correctly find the maximum matching.

Intuitive Proof: A leaf can only be matched with its parent or be discraded. If you match it with its parent, you get a profit (in matching number) of 1. If you discard it, then the only thing you gain is free-ing up the parent, but having a free parent clearly worth at most 1. This shows (Guaranteed Profit) >= (Maximum Potential Cost), so you can assume you always do it.

This is written in response to the first part of the article where you suggested Kuhn's algorithm.

→ Reply