<p>This is simply the maximum weight bipartite matching problem.</p>

<p>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. </p>

<p>You can use a min-cost flow algorithm to solve the problem. For more information you can see in <a href="https://en.wikipedia.org/wiki/Matching_(graph_theory)" rel="nofollow">https://en.wikipedia.org/wiki/Matching_(graph_theory)</a></p>

CC BY-SA 3.0
2016-08-17T04:11:21.713Z
2016-08-17T04:11:21.713Z
Mister R
<p>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.</p>

<p>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.</p>

<p>I've nicknamed this question the "Dance Partner Problem"</p>

<p>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.</p>

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

<p>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:</p>

<p>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 &amp; Woman=B the weight from this edge.</p>

<p>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</p>

<p>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.</p>

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

CC BY-SA 3.0
2016-08-16T23:50:05.483Z
Is this problem different than [maximum weight bipartite matching](https://en.wikipedia.org/wiki/Matching_(graph_theory)#In_weighted_bipartite_graphs)?
mhum
CC BY-SA 3.0
2016-08-17T14:43:42.200Z
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!
NateW
<np-complete><tsp>
Dance Partner Problem NP-completeness
NateW
# Dance Partner Problem NP-completeness

(Asked by: username_0 on 2016-08-16)

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?

**Tags:** np-complete, tsp

> **Comments:**
> **username_1**: Is this problem different than [maximum weight bipartite matching](https://en.wikipedia.org/wiki/Matching_(graph_theory)#In_weighted_bipartite_graphs)?  
> **username_0**: 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!  

---

## 1 answers

### Answer by username_2 on 2016-08-17. Score: 0 | Accepted answer

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


---

