Доказательство NP-полноты клика + независимый граф набора

Question

"Докажите, что NP-Complete определяет заданные входные данные G и k, имеет ли G как клику размера k, так и независимый набор размера k. Обратите внимание, что это 1 проблема, а не 2; ответ - да, если и только если G имеет оба этих подмножества."

Нам дали эту проблему в моем курсе алгоритмов, и большая группа студентов не могла понять это. Вот что мы имеем до сих пор...

Мы знаем, что как клика, так и задачи с независимыми множествами сами по себе являются NP-завершенными. Также известно, что проверка этой проблемы, учитывая некий "сертификат", есть в НП.

Проблема заключается в том, чтобы выполнить приведенную выше задачу (которая содержит как независимые множества, так и клики) как проблему, состоящую целиком из кликов или независимых множеств (по крайней мере, это то, что, по нашему мнению, нам нужно сделать). Мы не знаем, как выполнить это сокращение, не потеряв информацию, необходимую для того, чтобы вернуть сокращение к его первоначальной форме.

Answer 1

Подсказка: приведите CLIQUE к этой проблеме, добавив несколько вершин.

Answer 2

Спасибо "Moron" и "Rafal Dowgird" за подсказки! Исходя из этого, я думаю, что у меня есть решение. Пожалуйста, поправьте меня, если я ошибаюсь:

Так как мы уже знаем, что клика и задачи с независимым набором являются NP-Complete, мы можем использовать это в качестве основы для доказательства нашей проблемы. Давайте назовем нашу проблему проблемой Комбинированного Клик Независимого Набора (ИССА).

Предположим, нам дан граф G, у которого есть клика C размера k. Мы можем сократить этот граф до графа G' (читай: G prime), который имеет как клику C' размера k ', так и независимый набор I размера k', прикрепляя k вершин к каждой вершине в C. Это сокращение происходит в полиномиальное время с момента добавления вершин занимает O(n*k) времени (n вершин в графе и k вершин, прикрепленных к каждому узлу).

Обратите внимание, что C=C'и k=k'.

Теперь предположим, что нам дан граф G ', который имеет клику C' размера k 'и независимый набор I размера k', который определен как истинный. Сведение к проблеме клики является тривиальным, поскольку нам вообще не нужно изменять график, чтобы найти только клику.