如何为该匹配问题构造np约简? [英] how do I construct np-reduction for this matching problem?

问题描述

我有一个匹配的问题，我认为这很困难:

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

我相当确定这个问题是np完全的，但是我在寻找适当的减少量方面遇到了一些问题.该示例对应于以下(严重绘制)的图形:

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

推荐答案

减少派系问题

首先，请注意NP是一类决策问题，因此我们将问题调整为是否有表格安排?"而不是输出表布置".在实践中，当然没有真正的区别.

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.

现在，给定一个图，假设我们想知道是否存在至少大小为 k 的集团.这是(决定) clique问题，它是著名的NP完全问题之一.

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.

当且仅当您的匹配问题对同一个图具有大小为 k 的表有解决方案时，此图才会具有至少一个大小为 k 的集团.所有其他座位的座位应该不受限制，因此我们有 n-k 个单人桌.

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.

因此，我们可以创建一个匹配问题的实例，该实例等效于一个已知NP完全问题的实例.此实例的大小大致相同(没有指数爆炸)，因此这意味着减少，证明了匹配是NP难的.因为它在NP中也(很明显?)，它也是NP完整的.

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.

这篇关于如何为该匹配问题构造np约简?的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！