We're doing hobby events where people list their items followed by a wishlist of what they would like to receive in exchange for each one of their items, then the current algorithm finds the biggest trading cycles and people ship their items and receive what they matched with, if anything.

To do this we split every "item node" into two: an "item sender" and an "item receiver". Then if there were two items A and B, and the owner of B wants to exchange it for A, we would create an edge from $\texttt{A_sender}$ to $\texttt{B_receiver}$ with cost $1$. We do so for all trading wishes, and we also add a self edge from every sender to its own receiver, for example from $\texttt{A_sender}$ to $\texttt{A_receiver}$ with cost $INF$.

There's always a perfect bipartite matching in this graph, and the minimum cost one is the one that maximizes the number of real trades done. It's guaranteed to be a cycle because a node either matches with itself (and doesn't trade with anyone), or its sender matches with a different item's receiver, and that different item's sender can't match with itself, so it has to keep matching until it closes a cycle.

It's very common to see NP-hard problems clear out "but only if n >= 3". I've been wondering a lot, could it be possible to add a feature like "I would like to send these 2 items and receive this other item", and the opposite for it to make sense "I would like to send this item and receive these 2 others"?

I'm currently using Simplex network to solve the original problem, I tried building a construction on top of the original graph and I've seen stuff like Is "two or zero" matching in a bipartite graph NP complete? and tried using a Weigthed Blossom to formulate it as a general matching, but I just can't come up with a graph construction that makes sense with the cycles requirement (people only wanna send something and receive something in return).

Do you have any hints as if this could be a NP problem, or any intuition as to how I could try building a graph that could satisfy the new feature?

Thanks a lot!



Your Answer

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