0
$\begingroup$

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.

$\endgroup$
0
$\begingroup$

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)!

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ Thanks a lot! After thinking about the problem some more yesterday, I found out that all I really need to do is verify that a matching is maximum-weight perfect. If I can find that one of these problems that is NP-complete, then I should be able to verify whether or not a given the matching is maximum weight, perfect, correct? $\endgroup$ – Blake Holman Jun 15 at 13:24
  • $\begingroup$ Not at all. That’s more or less the same as the original problem. The decision problem would be “is there a matching of weight at least k?” That problem is in NP. If you’re given a matching and asked if it’s best, then that problem is still NP-hard. (If you were good at that, you could use that to make a poly-time algorithm to start with a matching and find a matching that does better. You could then iterate this to find a maximum-weight matching.) $\endgroup$ – Pat Devlin Jun 15 at 13:52
  • $\begingroup$ Oh of course. That makes sense now, I appreciate all the help! $\endgroup$ – Blake Holman Jun 15 at 14:05

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.