I really can't think of a concise way to phrase this problem, which makes it hard to search for, so forgive me if this is a duplicate question.

I've come across a problem and I would like to know if it is NP-Complete or not. If not, I'd like to know if there is a polynomial solution to it.

I've nicknamed this question the "Dance Partner Problem"

You have a set of men and a set of women on a team of dancers. The two sets are of equal size. Each pair of consisting of one man and one woman is capable of obtaining a certain score from the judges when they dance together. Find the pairing of men and woman such that the sum of the scores of each pair is maximized.

Proving that this problem is in NP is trivial (have a non-deterministic machine enumerate each pair combination and sum the scores).

My first instinct in reducing an NP-Complete problem to this problem was to reduce the traveling salesman problem on a weighted, directed graph as follows:

Create men and women 1-N where N is the number of nodes on the graph. Number the nodes on the TSP graph from 1 to N. For each edge on the graph: call the number of the start node A and the number of the end node B. Assign the score for the dance pair Man=A & Woman=B the weight from this edge.

Run the code to solve the dance partner problem. On the TSP graph, start at node 1. Repeat until you reach node 1 again: Look at current node number Find Man with the same number Find number of the man's partner Move to that node

However, I realized that this would only work if the optimal pairing of dance partners worked out so that there was never a circuit that didn't include all of the people. In other words if the optimal pairing for 4 pairs M1-W2, M2-W3, M3-W4, M4-W1 then this would work perfectly, but if the optimal paring was M1-W2, W2-M1, M3-W4, W4-M3, then our traveling salesman would get in a loop that did not cover all of the nodes.

Can anyone else come up with a proof of NP-completeness? Or perhaps can anyone find a deterministic polynomial solution?


closed as off-topic by Sasho Nikolov, Mohammad Al-Turkistany, Kaveh, Hsien-Chih Chang 張顯之, David Eppstein Aug 19 '16 at 4:42

This question appears to be off-topic. The users who voted to close gave this specific reason:

  • "Your question does not appear to be a research-level question in theoretical computer science. For more information about the scope, please see help center. Your question might be suitable for Computer Science which has a broader scope." – Sasho Nikolov, Mohammad Al-Turkistany, Kaveh, Hsien-Chih Chang 張顯之, David Eppstein
If this question can be reworded to fit the rules in the help center, please edit the question.

  • 4
    $\begingroup$ Is this problem different than maximum weight bipartite matching? $\endgroup$ – mhum Aug 16 '16 at 23:50
  • $\begingroup$ Yes. That is exactly what this problem is. I was hoping I would find that this was already a defined and well studied problem, I just didn't know a good name to search for. Thanks! $\endgroup$ – NateW Aug 17 '16 at 14:43

This is simply the maximum weight bipartite matching problem.

Suppose $G=(V=A \cup B,E)$ is the bipartite graph, between man dancers $A$ and women dancers $B$. We define a weight function over the edges $w:E \to R$, where $w(a,b)$ is the score of man $a$ dancing with women $b$. The goal is to find a matching $M$ with maximum score.

You can use a min-cost flow algorithm to solve the problem. For more information you can see in https://en.wikipedia.org/wiki/Matching_(graph_theory)


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