我如何为这个匹配问题构造 np-reduction？
how do I construct np-reduction for this matching problem?
我有一个匹配问题，我认为是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
我相当确定这个问题是 np-complete 的，但我在寻找适当的归约时遇到了一些问题。
该示例对应于以下（画得不好）图：
我对使用补充图减少到独立集有一个松散的想法。但我将非常感谢任何解决方案的想法
集团问题减少
首先，请注意 NP 是决策问题的 class，因此我们将问题调整为“是否有 table 安排？”而不是“输出 table 排列”。在实践中当然没有真正的区别。
现在，给定一个图，假设我们想知道是否存在至少大小为 k 的集团。这就是（决定）clique problem，这是著名的 NP 完全问题之一。
当且仅当您的匹配问题对同一个图有一个解决方案且 table 大小为 k 时，此图将至少有一个大小为 k 的团。所有其他人的座位应该不受限制，所以我们有 n-k 个座位 tables.
因此，我们可以创建一个匹配问题的实例，它等效于已知 NP 完全问题的任何实例。这个实例的大小大致相同（没有指数爆炸），所以这构成了一个缩减，证明匹配是 NP-hard 的。因为它在 NP 中也是（显然？），所以它也是 NP 完全的。
我有一个匹配问题，我认为是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
我相当确定这个问题是 np-complete 的，但我在寻找适当的归约时遇到了一些问题。 该示例对应于以下（画得不好）图：
我对使用补充图减少到独立集有一个松散的想法。但我将非常感谢任何解决方案的想法
集团问题减少
首先，请注意 NP 是决策问题的 class，因此我们将问题调整为“是否有 table 安排？”而不是“输出 table 排列”。在实践中当然没有真正的区别。
现在，给定一个图，假设我们想知道是否存在至少大小为 k 的集团。这就是（决定）clique problem，这是著名的 NP 完全问题之一。
当且仅当您的匹配问题对同一个图有一个解决方案且 table 大小为 k 时，此图将至少有一个大小为 k 的团。所有其他人的座位应该不受限制，所以我们有 n-k 个座位 tables.
因此，我们可以创建一个匹配问题的实例，它等效于已知 NP 完全问题的任何实例。这个实例的大小大致相同（没有指数爆炸），所以这构成了一个缩减，证明匹配是 NP-hard 的。因为它在 NP 中也是（显然？），所以它也是 NP 完全的。