Graph Matching

3D Matching

2D matching

• Input: 2 sets $X,Y$ of size $n$ and a family of edges $E\subset X\times Y$
• Output: is there a perfect matching ($n$ edges that cover $X,Y$)?
• This is testing if a bipartite graph has a perfect matching

3D matching

• Input: 3 sets $X,Y,Z$ of size $n$ and a family of hyperedges $E\subset X\times Y\times Z$
• Output: is there a perfect matching ($n$ hyperedges that cover $X,Y$ and $Z$)? (each $x_i$ (and each $y_j$ , and each $z_k$) is in a unique hyperedge)
• NP