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?

  • 2
    $\begingroup$ 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! $\endgroup$
    – Kaveh
    Commented Apr 3, 2012 at 22:26
  • $\begingroup$ Thanks. Preliminary googling with the name you suggest hasn't yielded anything. I'd appreciate if anyone can provide their inputs. $\endgroup$
    – Ankur
    Commented Apr 4, 2012 at 2:52


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.