<p>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 <a href="https://mathoverflow.net/questions/92962/k-uniform-k-partite-hypergraph-matching-in-polynomial-time">Mathoverflow</a>.</p>

<p>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?</p>

CC BY-SA 3.0
2012-04-03T22:26:42.350Z
posted on behalf of [Yixin Cao](http://cstheory.stackexchange.com/users/7059/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!
Kaveh
CC BY-SA 3.0
2012-04-04T02:52:25.433Z
Thanks. Preliminary googling with the name you suggest hasn't yielded anything. I'd appreciate if anyone can provide their inputs.
Ankur
<ds.algorithms><graph-theory><co.combinatorics><hypergraphs>
k-uniform k-partite hypergraph matching in polynomial time
Ankur
# k-uniform k-partite hypergraph matching in polynomial time

(Asked by: username_0 on 2012-04-03)

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](https://mathoverflow.net/questions/92962/k-uniform-k-partite-hypergraph-matching-in-polynomial-time).

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?

**Tags:** ds.algorithms, graph-theory, co.combinatorics, hypergraphs
> **Comments:**
> **username_1**: posted on behalf of [Yixin Cao](http://cstheory.stackexchange.com/users/7059/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!  
> **username_0**: Thanks. Preliminary googling with the name you suggest hasn't yielded anything. I'd appreciate if anyone can provide their inputs.  

---

## 0 answers

