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?
 A: I'm assuming that by matching number, you mean the maximum number of pairwise disjoint edges. There are a few viewpoints you might want to try. One is that the maximum matching is the same as the maximum independent set of the dual hypergraph. (Hypergraphs have weak independent sets where no edge is completely contained, and strong independent sets where you pick no two points from any edge; here I mean strong.) Moreover, the independent sets of a hypergraph are the same as the independent sets of the 1-skeleton (where every hyperedge is replaced by a clique). So possibly, there are classes of graphs for which independent set is polynomial-time solvable, which have an interpretation as coming from 3-partite 3-uniform hypergraphs. Bounded treewidth is one concrete example to try.
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.
If you're looking for leads I would suggest "Hypergraphs," Part VIII of Schrijver's Combinatorial Optimization book. It discusses what properties of hypergraphs are sufficient to give poly-time solutions to basic quantities such as the matching number.
