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
    Apr 3 '12 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
    Apr 4 '12 at 2:52

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.