Докажите NP-комплектность CLIQUE-OR-INDEPENDENT-SET

Question

Прежде всего, я хочу упомянуть, что это моя домашняя работа . Однако, чтобы решить мою проблему, я могу использовать любую литературу, которую хочу.

Несмотря на то, что я думаю, что эта проблема ясна из его названия, я дам ей описание: «Для заданного неориентированного графа G и заданного целого k G содержит полностью связный (клик) подграф размера k или полностью несвязный подграф (независимый набор) размера k. "

Я знаю о полиномиальных сокращений от 3-SAT до CLIQUE и от 3-SAT до INDEPENDENT-SET. (http://mlnotes.com/2013/04/29/npc.html) Однако у меня проблема с этим, потому что я не могу объединить эти два сокращения. Я также пытался сократить с CLIQUE до CLIQUE-OR-INDEPENDENT-SET, но без особого успеха.

Так что я был бы очень признателен за любые намеки!

Заранее спасибо.

Answer 1

Я выяснил уменьшение из проблема INDEPENDENT-SET до CLIQUE-OR-INDEPENDENT-SET. Все, что вам нужно сделать, это добавить n изолированные вершины в граф G (который является экземпляром INDEPENDENT-SET и имеет n вершин). Позвольте называть этот вновь созданный граф G' (пример CLIQUE-OR-INDEPENDENT-SET). Тогда нетрудно доказать, что G имеет k независимый комплект iff G' имеет n+k независимый набор клики (так как по конструкции он не может иметь n+k clique).