# k-uniform k-partite hypergraph matching in polynomial time

I have what seems like an elementary question, but google didn't throw up any answers for it. I would appreciate any pointers users here may provide. Please note that I have also asked this question on Mathoverflow.

It is well known that for $k\geq 3$ finding the matching number of a $k$-uniform $k$-partite hypergraph is NP hard in general. Are there subclasses of these hypergraphs for which the problem is solvable in polynomial time?

• posted on behalf of Yixin Cao: I didn't try to google but I guess the reason of no-answer-found might be the name you used. This problem is more commonly known as "(maximum) k-dimensional matching", and its special case of k=3 was actually among the six basic problems of Garey&Johnson's list. Good luck! – Kaveh Apr 3 '12 at 22:26
• Thanks. Preliminary googling with the name you suggest hasn't yielded anything. I'd appreciate if anyone can provide their inputs. – Ankur Apr 4 '12 at 2:52