ПОЛУКЛИКА – NP Полная задача

Question

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

Пусть Half-Clique = {$ langle G rangle $ | $ G $ - это неправомерный график, имеющий полный подграф с узлами $ n/2 $, где n - количество узлов в $ g $}.Докажите, что ПОЛУКЛИКА NP-полна.

Также мне известно следующее:

• С точки зрения этой проблемы А. клика, определяется как неориентированный подграф входного графа, в котором каждые два узла соединены ребром.А $k$-клика — клика, содержащая $k$ узлов.
• По нашему учебнику Майкла Сипсера "Введение в теорию вычислений", стр. 268, что проблема CLIQUE = {$\langle G,k angle$ | $G$ — неориентированный граф с $k$-кликой} находится в NP
• Кроме того, согласно тому же источнику (на стр. 283) отмечается, что CLIQUE находится в NP-Complpete (таким образом, очевидно, также в NP).

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

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

Для меня это звучит правильно, но я пока не очень доверяю себе в этом предмете.Еще раз хочу всем напомнить это ЗАДАЧА НА ДОМАШНЕМ ЗАДАЧЕ поэтому, пожалуйста, постарайтесь избежать ответа на вопрос.Любое руководство, которое не соответствует этому, будет только приветствоваться!

Answer 1

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

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

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

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

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

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

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

Другими словами, мы должны показать, что мы можем решить КЛИКУ, если мы можем решить ПОЛУКЛИКУ.Мы делаем это, показывая, что для каждого экземпляра CLIQUE мы можем спроектировать экземпляр HALF-CLIQUE так, чтобы экземпляр CLIQUE был экземпляром «да», если и только если экземпляр HALF-CLIQUE является экземпляром «да».

Таким образом, доказательство начинается так:учитывая граф $G=(V, E)$, я могу создать некоторый граф $H=(V', E')$ такой, что $G$ содержит $k$-клику тогда и только тогда, когда $H$ содержит $n/ 2$-клика.Эту часть я оставлю вам (это та часть, которая требует творческого подхода, та часть, которая касается конкретной проблемы).

Answer 2

Ты выглядишь немного потерянным.Вы хотите показать, что HALF-CLIQUE $\ge$ CLIQUE, а это означает, что вы ищете многовременной алгоритм, который принимает экземпляры CLIQUE в качестве входных данных и выводит экземпляры HALF-CLIQUE со свойством, которое входные данные «да» отображают на « Входные данные «да» и «нет» сопоставляются с «нет».

Итак, по сути, задача состоит в том, чтобы взять граф $G$ и число $k$ и вывести новый граф $H$ (и без числа) так, чтобы $H$ имел клику по крайней мере в половине своих вершин всякий раз, когда $ В G$ есть клика размера $k$.

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

Попробуйте создать $H$, присоединив (каким-либо образом) к $G$ клику подходящего размера, а также некоторое количество ни с чем не связанных вершин.

Answer 3

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