ПОЛОВИНА КЛИК - NP Полная задача

20

Позвольте мне начать с замечания, что это домашняя проблема. Пожалуйста, предоставьте только рекомендации и соответствующие замечания, НИКАКИХ ПРЯМЫХ ОТВЕТОВ, пожалуйста . С учетом сказанного, вот проблема, на которую я смотрю:

Пусть HALF-CLIQUE = { | G является неориентированным графом, имеющим полный подграф с по крайней мере n / 2 узлами, где n - количество узлов в G }. Покажите, что ПОЛОВИНКА является NP-полной.GGn/2G

Также я знаю следующее:

  • В терминах этой проблемы клика определяется как неориентированный подграф входного графа, в котором каждые два узла соединены ребром. -cliquek является кликой , который содержит узлов.k
  • По нашему учебнику, Майкл Сипзер в « Введение в теорию вычислений », стр 268, что проблема CLIQUE = { | G неориентированный граф с k- кликом} находится в NPG,kGk
  • Кроме того, согласно тому же источнику (на стр. 283), отмечает, что CLIQUE находится в NP-Complpete (таким образом, также очевидно, в NP).

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

Хорошо, сначала я бы отметил, что сертификат будет просто ПОЛОВИННЫМ QLIQUE . Теперь кажется, что мне нужно было бы создать верификатор, который является полиномиальным сокращением времени с CLIQUE (мы знаем, что NP-Complete) до HALF-CLIQUE. Моя идея состояла бы в том, чтобы это было сделано путем создания машины Тьюринга, которая запускает верификатор машины Тьюринга в книге для CLIQUE с дополнительным ограничением для HALF-CLIQUE.sizen/2

Это звучит правильно для меня, но я пока не очень доверяю себе в этом вопросе. Еще раз, я хотел бы напомнить всем, что это ПРОБЛЕМА ДОМАШНЕГО РАБОТЫ, поэтому, пожалуйста, постарайтесь не отвечать на вопрос. Любое руководство, которое не соответствует этому, будет приветствоваться!

BrotherJack
источник

Ответы:

15

Судя по вашему описанию и комментариям, вам лучше всего поможет точное описание того, как сокращения могут быть использованы для доказательства NP-полноты:

Проблема является NP-полной, если она находится в NP, и она NP-сложная. Это означает, что любое доказательство NP-полноты состоит из двух частей: доказательство того, что проблема лежит в NP, и доказательство того, что оно NP-сложно.

Для первой части вы должны показать, что экземпляры YES могут быть проверены за полиномиальное время с использованием некоторого подходящего сертификата. Кроме того, вы можете показать, что проблема может быть решена за полиномиальное время с помощью недетерминированной машины Тьюринга, но обычно это не делается, поскольку ошибки легко допускаются.

В вашем случае это сводится к доказательству того, что для каждого графа с -кликом вы можете найти какое-то доказательство того, что действительно есть такая клика, такая, что, вооружившись таким доказательством, вы можете проверить за полиномиальное время, что действительно есть такая клика.n/2

Во второй части вы должны показать, что проблема NP-сложная. Это почти во всех случаях доказывается тем, что ваша проблема, по крайней мере, так же сложна, как и некоторые другие проблемы NP-hard. Если HALF-CLIQUE такой же твердый, как CLIQUE, он также должен быть NP-hard.

Вы делаете это, доказывая сокращение ОТ КЛИК, ДО ПОЛОВИНЫ. Вы «уменьшаете» проблему, делая ее «проще». Вы говорите: «Решить CLIQUE сложно, но я доказал, что вам нужно решить только HALF-CLIQUE, чтобы решить CLIQUE». (многие люди, даже эксперты, иногда говорят, что это неправильно :))

Существуют различные типы сокращений: сокращение, которое наиболее часто используется, - это то, где вы отображаете экземпляры CLIQUE в этом случае на экземпляры HALF-CLIQUE, размер которых не более чем на полиномиально больше, за полиномиальное время. Это означает, что если мы можем решить ПОЛОВИНУ-КЛИК, то мы также можем решить КЛИК, связав алгоритм и редукцию.

Другими словами, мы должны показать, что мы можем решить CLIQUE, если мы можем решить HALF-CLIQUE. Мы делаем это, показывая, что для каждого экземпляра для CLIQUE мы можем спроектировать экземпляр HALF-CLIQUE таким образом, чтобы экземпляр CLIQUE был экземпляром 'yes', если экземпляр HALF-CLIQUE является экземпляром 'yes'.

G=(V,E)H=(V,E)GkHn/2

Алекс тен Бринк
источник
Отлично настроено, я думаю, вы проделали отличную работу, предоставив достаточно информации, чтобы направлять ее, не давая ответа и делая это красноречиво. Спасибо.
BrotherJack
1
Нечто подобное должно быть помещено в тэг вики np-complete для дальнейшего использования. Вы не возражаете?
Рафаэль
8

GkHHGk

Спойлер ниже содержит подсказку о том, как выполнить это сокращение:

HG

Луис
источник
Я не понимаю, что вы говорите. Я попытался уменьшить HALF-CLIQUE до CLIQUE, изменив модификатор, использованный в книге, чтобы доказать, что CLIQUE был NP, запустить его на входном графе G, и если он найдет проверку CLIQUE, чтобы увидеть, содержит ли этот CLIQUE по крайней мере n / 2 узлов, где n - количество узлов в G. Разве такой верификатор HALF-CLIQUE не показывает, что верификатор CLIQUE является его сокращенной формой (как в подзадаче решения HALF-CLIQUE )?
BrotherJack
Или вы говорите, что у меня это задом наперед и нужно доказать, что КЛИК должен быть уменьшен до ПОЛОВИНЫ? Я также совершенно не получаю ваш спойлер. Есть ли способ объяснить это, не раздавая ответ?
BrotherJack
3
Да, чтобы показать проблему является NP-полной, вам нужно (а) показать , что в НП и (б) уменьшить некоторые известную NP-трудной задачей для него. Чтобы запомнить правильное направление для сокращения, смысл состоит в том, чтобы использовать новую проблему в качестве «черного ящика» для эффективного решения известной проблемы NP-C.
Луи
Хорошо, я думаю, что теперь понимаю. Спасибо за вашу помощь!
BrotherJack
+1 Я думаю, что понял. Ваш намек был очень поучительным, когда я понял, что я делаю неправильно. Еще раз спасибо!
BrotherJack
0

Вы можете уменьшить от проблемы покрытия вершины. Если граф дополнения данного графа имеет покрытие вершин меньше, чем n / 2 узлов, то этот граф будет иметь клику более чем n / 2 узлов, то есть он будет полукликой. Просто заявите, что проблему с вершинным покрытием трудно решить, и это так.

Arnav
источник
1
Поскольку вы можете уменьшить любую NP-полную проблему, это не очень полезно. Подробности о снижении ожидаются.
Рафаэль
n/2