Here's a problem that came up when organizing a party:

You need to place $n$ guests in tables of size 10. Each guest has a list of $m$ other guests they'd like to have in their table. Find a seating arrangement so that the number of granted wishes is maximized.

As many tables as possible should be full, i.e. at most one table can have less than 10 guests.

We tried to formulate it as a directed graph problem where for each guest there's a corresponding vertex in $V$. The edges represent wishes of the guests, i.e. there's an edge $(u, v) \in E$ if guest $u$ wishes to sit next to guest $v$. Note that this does not imply $(v, u) \in E$ because the wish might not be mutual.

Now finding the seating arrangement could be thought of as finding $m/10$ sets of 10 vertices where each set is as close to a fully connected clique as possible. This way we maximize the happiness of the guests. Another way of looking at it would be minimizing the number of outgoing arcs from each set.

To me this sounds very difficult, but I couldn't find a satisfying problem which I could use in a NP-hardness reduction proof. I noticed that this is pretty close to a K-clique densest subgraph problem, but that is also only about undirected graphs.

Is there a way to formulate this as a problem with an undirected graph, or some other problem related to cliques I am missing?


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.