Polynomial time algorithm - Matching pairs of vertices

Question

Let T be a tree with root r and S a set with an even number of vertices of T. Design a polynomial time algorithm that finds |S|/2 simple and disjoint paths in edges matching pairs of vertices in S. The following figure shows an example in which S consists of the six vertices enclosed in circles and three paths (denoted by three different types of dotted lines) that match those vertices.

Hint: Gain intuition by making instances like the one in the figure and observing what happens when you walk the entire border of the tree almost touching it, but not really doing that; then think about how to express the idea of such walk with a recursive algorithm.

I tried to analyze the problem but I don't really understand how to express it as a recursive algorithm, could you help me, please?

Answer 1

The idea is to use recursion. Let us suppose that the children of the root $r$ are $v_1,\ldots,v_d$, and let $S_1,\ldots,S_d$ consist of those elements of $S$ in the subtree rooted at $v_1,\ldots,v_d$, respectively.

One easy case is when $r \notin S$ and $|S_i|$ is even for all $i$. In this case, we can simply recurse on the subtrees. There are two complications that arise in the general case:

1. Some $|S_i|$ might be odd.
2. The root might belong to $S$.

The two complications are related, but let us tackle them one by one. Suppose first that $r \notin S$. If $|S_i|$ is odd for some $i$, then we would like to fix that. The only reasonable way is to add $v_i$ to $S_i$ if $v_i \notin S_i$, and to remove $v_i$ from $S_i$ is $v_i \in S_i$. We now solve the modified problem recursively, and have to somehow derive a solution for the original problem.

Let us introduce some notation: $O$ is the set of $i$ such that $|S_i|$ is odd, and $S'_i$ is the set $S_i$ after modification (adding or removing $v_i$). Consider a solution for the new instance. We will derive a solution for the original instance by pairing up the indices in $O$. Suppose that we chose to pair $i,j$, and consider the solutions for $S'_i,S'_j$. There are three cases to consider:

1. $v_i \in S_i$ and $v_j \in S_j$. In this case we add a path from $v_i$ to $v_j$ via $r$.
2. $v_i \notin S_i$ and $v_j \notin S_j$. In this case we add a path from $v_i$ to $v_j$ and "erase" $v_i,v_j$. That is, in the solution to the new problem, $v_i$ is connected to some $w_i$ in its subtree, and $v_j$ is connected to some $w_j$ in its subtree. We connect $w_i$ and $w_j$ via the path $w_i-v_i-r-v_j-w_j$.
3. $v_i \in S_i$ and $v_j \notin S_j$. In this case we add a path from $v_i$ to $v_j$ and "erase" $v_j$. That is, in the solution to the new problem, $v_j$ is connected to some $w_j$ in the subtree. We connect $v_i$ and $w_j$ via the path $v_i-r-v_j-w_j$.

When $r \in S$, we only have to modify the above strategy a little. We arbitrarily pair $r$ with some $i \in O$, and then proceed much as above. This time there are only two cases:

1. $v_i \in S_i$. In this case we simply connect $r$ and $v_i$.
2. $v_i \notin S_i$. In this case we add the edge between $r$ and $v_i$ and "erase" $v_i$. That is, in the solution to the new problem, $v_i$ is connected to some $w_i$ in its subtree. We connect $r$ and $w_i$ via the path $r-v_i-w_i$.