CODEWITHSUNDEEP
algorithmgraphmatchingbipartite
entangledgravitationalcollapse
entangledgravitationalcollapse

Reputation: 9

Bipartite seating arrangement on round tables

Imagine we have two groups, women and men. Each women has a set of men they are interested. We represent their interest as edges in a bipartite graph.

Now, we are trying to set up everyone in round tables, such as if you go around the table, each seat will pair of seats will be occupied by a couple with a connection. So, if you go clockwise around the table, for example, a seat may have a woman that is interested on a man seating on the next seat, and this may will also be the interest of the woman sitting on the next seat, and so forth. Each table needs to have at least a number k of guests.

I am trying to design an algorithm using max flow to satisfy those requirements and I would really appreciate some ideas

Upvotes: 0

Views: 375

Answers (1)

templatetypedef
templatetypedef

Reputation: 373082

This problem is in general NP-hard. Imagine that you have a graph with 2n nodes and that you only have one table of size 2n. Now, there's a way to seat everybody around the table in the way you'd like if and only if the graph has a Hamiltonian cycle. Since the Hamiltonian cycle problem on bipartite graphs is NP-hard, your problem is NP-hard as well. As a result, I doubt there's a nice way to use max-flow to solve this particular problem unless you build an exponentially-large graph.

Upvotes: 1

Related Questions