algorithm - how do I construct np-reduction for this matching problem?

Question

I have a matching problem, which I think is np-hard:

We need to arrange a dinner for a group of n people, some of the people are friends with eachother, some are not. We need to sit everyone at a table, but they should never sit with someone that they are not friends with. There are *k* tables K = r1+r2+···+rk=n.

**Input**
input is formatted as one first line k, then follow one line of k numbers, where each number represents a table and it's capacity. Then comes n lines of people, where we can see friendships of person i. All friendships are mutual.

**Output**

Output the formations of people that can be seated together, without having to sit with someone that they are not friends with

 example: 
 Input:
 2
 3, 3
 Alice:  Bob, Claire, Eric, Juliet, Romeo
 Bob:  Alice, Claire, Juliet, Romeo
 Claire:  Alice, Bob, Juliet
 Eric:  Alice, Romeo
 Juliet:  Alice, Bob, Claire
 Romeo:  Alice, Bob, Eric

 Output:
 Romeo, Eric, Alice 
 Bob, Claire, Juliet

Im fairly certain that this problem is np-complete, but I am having some problems finding a proper reduction. The example corresponds to the following (badly drawn)graph:

I have a loose idea around using a complimentary graph to reduce to independent set. but i would be very gratefull for any ideas for solutions

Answer 1

Clique problem reduction

First off, note that NP is a class for decision problems, so we'll adjust the question to "is there a table arrangement?" instead of "output the table arrangement". In practice there is of course no real difference.

Now, given a graph, let's say we want to know if there is a clique of at least size k. This is the (decision) clique problem, which is one of the famous NP-complete problems.

This graph will have at least one clique of size k if and only if your matching problem has a solution for the same graph, with a table of size k. The seating for all the others should be unconstrained, so we have n-k one-seat tables.

Thus, we can create an instance of the matching problem that is equivalent to any instance of a known NP-complete problem. This instance is roughly the same size (no exponential blow-up), so this constitutes a reduction, proving that the matching is NP-hard. As it is also (clearly?) in NP, it is also NP-complete.