Last month I discovered a nice question on stackoverflow and thought the 1,n matching problem could be solved via introducing a 1,k tree matching. Look here for my question, but as Moron pointed out this is not solvable in polynomial time.

Now I discovered mathoverflow and would like to know if one could reduce some possibilities or if one could introduce some restrictions so that the 1,n matching could be solved in polytime. Do you have an idea?

Background: I would like to implement a heuristic for that problem. At the moment I am using an algorithm based on the GPA heuristic for weighted maximum matchings in general graphs as described here.

Missing tag: matching