Блог

У меня есть проблема с сопоставлением, которая, я думаю, является np-сложной:

 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-полной, но у меня возникли некоторые проблемы с поиском правильного сокращения.
Пример соответствует следующему (плохо нарисованному) графику:

У меня есть свободная идея об использовании дополнительного графика для сведения к независимому множеству. но я был бы очень благодарен за любые идеи для решений

Сокращение проблемы с кликами

Прежде всего, обратите внимание, что NP — это класс для задач принятия решений, поэтому мы изменим вопрос на «есть ли расположение таблиц?» вместо «вывести расположение таблиц». На практике, конечно, нет реальной разницы.

Теперь, учитывая график, допустим, мы хотим знать, существует ли клика хотя бы размера k . Это проблема клики (решения), которая является одной из известных NP-полных задач.

Этот граф будет иметь хотя бы одну клику размера k тогда и только тогда, когда ваша задача сопоставления имеет решение для того же графика с таблицей размеров k . Места для всех остальных должны быть свободными, поэтому у нас есть n-k столы на одно место.

Таким образом, мы можем создать экземпляр задачи сопоставления, эквивалентный любому экземпляру известной NP-полной задачи. Этот экземпляр имеет примерно тот же размер (без экспоненциального увеличения), так что это представляет собой сокращение, доказывающее, что сопоставление является NP-жестким. Поскольку это также (очевидно?) В NP, оно также является NP-полным.