Hamiltonian Spanning Tree cf-618D

This is two separate problems: One where X > Y and when X <= Y.

Suppose X > Y. Then, we can almost always choose a path that avoides any spanning tree edges. There is one tricky case, which is the case of a star graph.

To prove the above statement, we know a tree is bipartite, so let's choose a bipartition X,Y. As long as there is exists a pair x in X and y in Y such that there isn't an edge between x and y, we can form a hamiltonian path without visiting any spanning tree edges (i.e. travel through all vertices in X and end at x, then go to y, then travel through all vertices in Y). We can see that this happens as long as it is not a complete bipartite graph, which can only happen when |X| = 1 or |Y| = 1 (which is the case of a star graph).

For the other case, X <= Y. Some intuition is that you want to maximize the number of edges that you use within the spanning tree. So, you might think along the lines of a "maximum path cover". Restating the problem is a good idea at this point.

Here's a restated version of the problem. You're given a tree. Choose the maximum number of edges such that all nodes are incident to at most 2 edges. (or equivalent a "2-matching" in this tree). Roughly, the intuition is that a 2-matching is a path cover, and vice versa.

This can be done with a tree dp, but here is a greedy solution for this problem. Root the tree arbitrarily. Then, let's perform a dfs so we process all of a node's children before processing a node. To process a node, let's count the number of "available" children. If this number is 0, then mark the node as available. If this number is 1, draw an edge from the node to its only available child and mark the node as available. Otherwise, if this number is 2 or greater, choose two arbitrary children and use those edges. Do not mark the node as available in this case.

Now, let U be the number of edges that we used from the above greedy algorithm. Then, the final answer is (n-1-U)*y + U*x).