Let $H=(V, E)$ be a weighted hypergraph such that $V=A\cup B \cup C$, where $A,B,C$ are disjoint sets of size $n$, and $E=A\times B\times C$. In my particular case, $\forall e\in E$, $ wt(e)\in\{0,\pm 1, \pm 3\}$.


**I'm trying to figure out whether or not there is an efficient algorithm to compute the maximum cardinality perfect matching for this case.** I've attempted generalizing max-flow, for this constrained case, but I didn't really get anywhere. I also tried translating it to a classical graph, since we have a lot of tools to deal with those. For example, I let the vertices correspond to the edges of $H$, and having an edge connect two vertices if they map to disjoint edges in $H$. Then the weights correspond to the sum of the weights of the vertices in the new graph (the weights of the edges in hypergraph). The issue with this is that I'm unsure exactly how to characterize the optimal solution in this way. It is clear that I'm trying to find the maximum weight $n$-length path that corresponds to disjoint edges in $H$, but I'm not sure how to start finding an efficient algorithm for that.


If you know the answer then a hint is fine, but I'm mostly concerned if this is already known to be NP-complete. 



Maximum-weight perfect matching in a 3-regular, complete, 3-partite hypergraph
Yup, NP-hard.


Consider the case where edges only have two weights. Then we have a hypergraph of light edges, and the problem is to pick a matching using as many light edges as possible. This is NP-hard, and in fact I believe it was one of Karp’s original 21 NP-complete problems.


<https://en.m.wikipedia.org/wiki/3-dimensional_matching>


That said, you might still want to solve this problem, in which case a lot is known. There are analyses of random-type strategies (also if the edge weights are random) as well as Dirac-type results (“if there are lots of light edges, then...”).


There are also results on fractional matchings if that floats your boat. Those are easier of course.


But yea. Matchings in graphs are actually fine, but matchings in hypergraphs are suddenly much harder (even in the $r$-partite case)!


