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

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

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


algorithm np-complete
person lazycamper    schedule 08.05.2020    source источник
comment
Похоже, если вы дополните график, вы будете искать клики размером как минимум k ... См. stackoverflow.com/questions/2801138/   -  person Jean-Baptiste Yunès    schedule 08.05.2020

Ответы (1)


arrow_upward
0
arrow_downward

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

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

person templatetypedef    schedule 08.05.2020