## 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 that MO users may provide.

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?

-
 Just to clarify: By matching number, do you mean the number of perfect matchings in the hypergraph? Or whether the hypergraph has a matching or not? – Zur Luria Apr 5 2012 at 13:22 By matching number I mean finding the largest number of pairwise disjoint hyperedges. – Ankur Apr 18 2012 at 22:25

One class of hypergraphs where matching is in P, is for interval hypergraphs. But, the class of 3-partite 3-uniform interval hypergraphs is very limited. Here's one more general class that is poly-time solvable: the set of 3-partite 3-uniform hypergraphs where each of the 3 vertex parts have labels ${1, 2, ..., n/3},$ and where for every edge the labels of its three vertices are within a constant distance of each other. You can show using dynamic programming that the matching problem is solvable here in polynomial time. On the other hand, that's not really making essential use of the 3-partite or 3-uniformness.