Позвольте мне начать с замечания, что это домашняя проблема. Пожалуйста, предоставьте только рекомендации и соответствующие замечания, НИКАКИХ ПРЯМЫХ ОТВЕТОВ, пожалуйста . С учетом сказанного, вот проблема, на которую я смотрю:
Пусть HALF-CLIQUE = { | G является неориентированным графом, имеющим полный подграф с по крайней мере n / 2 узлами, где n - количество узлов в G }. Покажите, что ПОЛОВИНКА является NP-полной.
Также я знаю следующее:
- В терминах этой проблемы клика определяется как неориентированный подграф входного графа, в котором каждые два узла соединены ребром. -clique является кликой , который содержит узлов.
- По нашему учебнику, Майкл Сипзер в « Введение в теорию вычислений », стр 268, что проблема CLIQUE = { | G неориентированный граф с k- кликом} находится в NP
- Кроме того, согласно тому же источнику (на стр. 283), отмечает, что CLIQUE находится в NP-Complpete (таким образом, также очевидно, в NP).
Я думаю, что у меня есть ядро ответа здесь, однако я мог бы использовать некоторые указания на то, что с ним не так, или любые связанные с этим вопросы, которые могут иметь отношение к ответу . Это общая идея, которую я имею до сих пор,
Хорошо, сначала я бы отметил, что сертификат будет просто ПОЛОВИННЫМ QLIQUE . Теперь кажется, что мне нужно было бы создать верификатор, который является полиномиальным сокращением времени с CLIQUE (мы знаем, что NP-Complete) до HALF-CLIQUE. Моя идея состояла бы в том, чтобы это было сделано путем создания машины Тьюринга, которая запускает верификатор машины Тьюринга в книге для CLIQUE с дополнительным ограничением для HALF-CLIQUE.
Это звучит правильно для меня, но я пока не очень доверяю себе в этом вопросе. Еще раз, я хотел бы напомнить всем, что это ПРОБЛЕМА ДОМАШНЕГО РАБОТЫ, поэтому, пожалуйста, постарайтесь не отвечать на вопрос. Любое руководство, которое не соответствует этому, будет приветствоваться!
источник
Спойлер ниже содержит подсказку о том, как выполнить это сокращение:
источник
Вы можете уменьшить от проблемы покрытия вершины. Если граф дополнения данного графа имеет покрытие вершин меньше, чем n / 2 узлов, то этот граф будет иметь клику более чем n / 2 узлов, то есть он будет полукликой. Просто заявите, что проблему с вершинным покрытием трудно решить, и это так.
источник