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?