Докажите, что конкретное c решение проблемы является NP-полной

Question

• Дано: граф G
• Ввод: k
• Возврат: «ДА», если существует набор из k узлов, такой, что ни два узла не соединены, ни два узла подключены к одному узлу. Например, если (A, B) и (B, C), то A и C не допускаются в наборе из k узлов. Как мы можем доказать, что эта проблема является NP-полной?

РЕДАКТИРОВАТЬ: Я предполагаю, что мы могли бы использовать независимое множество / вершинное покрытие?

Answer 1

Полагаю (?) Это домашнее задание.

В качестве подсказки начните с проблемы доминирующего набора .