CODEWITHSUNDEEP
algorithmtree
Stefan Kendall
Stefan Kendall

Reputation: 67832

How do I test whether a tree has a perfect matching in linear time?

Give a linear-time algorithm to test whether a tree has a perfect matching, that is, a set of edges that touches each vertext of the tree exactly once.

This is from Algorithms by S. Dasgupta, and I just can't seem to nail this problem down. I know I need to use a greedy approach in some manner, but I just can't figure this out. Help?

Pseudocode is fine; once I have the idea, I can implement in any language trivially.

The algorithm has to be linear in anything. O( V + E ) is fine.

Upvotes: 3

Views: 11255

Answers (5)

Aleksandra Sikora
Aleksandra Sikora

Reputation: 31

The working algorithm would be something as follows:

For each leaf in the tree: 
  add edge from leaf to its parent to the solution
  delete edge from leaf to its parent
  delete all edges from the parent to any other vertices
  delete leaf and parent from the tree

If the tree is empty then the answer is yes. Otherwise, there's no perfect matching.

Upvotes: 0

user487478
user487478

Reputation: 391

In the case of a "graph", The first step of the problem should be to find the connected components.

Since every edge in the final answer connect two vertices, they belong to at most one of the connected components.

Then, the perfect matching could be found for each connected component.

Upvotes: 1

Adam
Adam

Reputation: 786

I think that it's a simplified problem of finding a Hamiltonian path in a graph: http://en.wikipedia.org/wiki/Hamiltonian_path

http://en.wikipedia.org/wiki/Hamiltonian_path_problem

I think that there are many solutions on the internet to this problem, but generally finding Hamilton cycle is a NP problem.

Upvotes: -1

Stefan Kendall
Stefan Kendall

Reputation: 67832

I think I have the solution. Since we know the graph is a tree, we know of the existance of leaf nodes, nodes with one edge and no children. In order for this node to be included in the perfect matching, that edge MUST exist in the final solution.

Ergo, we can find all edges connecting to a leaf node, add to the solution, and remove the touched edges from the graph. If, at the end of this process, we are left any remaining nodes untounched, there exists no perfect matching.

Upvotes: 7

Charlie Martin
Charlie Martin

Reputation: 112366

Linear in what? Linear in the number of edges, keep the edges as an ordered incidence list, ie, every edge (vi, vj) in some total order. Then you can compare the two lists in O(n) of the edges.

Upvotes: -1

Related Questions