6
$\begingroup$

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?

Improve this question
$\endgroup$
2
  • 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, 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
    Apr 4, 2012 at 2:52

0

Reset to default

Your Answer

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