Докажите, что задача, состоящая из клики и независимого множества, является NP-полной.

Опубликовано: 19 Сентября, 2022

Условие: NP-полнота, NP-класс, клика, независимый набор

Задача: Для заданного неориентированного графа G = (V, E) и целого числа K определить, существует ли клика размера K , а также независимое множество (IS) размера K. Продемонстрируйте, что это NP Complete.

Объяснение:

A Clique is a subgraph of a graph in which all of the vertices are connected, forming a complete graph. The Clique Decision Problem involves determining whether or not a clique of size K exists in the given graph.

An Independent SetS of graph G = (V, E) is a collection of vertices in the graph G = (V, E) where no two vertices are adjacent.

Данная проблема Clique + IS представляет собой комбинацию как Clique, так и независимого набора, и может быть описана следующим образом:

  • Входные данные — график G (V, E) и целое число K
  • Выход – клика и независимое множество размера K

To prove a problem NP Complete, there are two steps involved:

  1. Prove given problem belong to NP Class
  2. All other problems in the NP class can be polynomial time reducible to that problem. (This is the prove of being NP-Hard)

Now it is not possible to reduce every NP problem to another NP problem to prove it’s NP completeness all the time. That’s why we show that any known NP complete problem is reducible to that problem in polynomial time.

Доказательство:

1.Clique+IS относится к классу NP:

Говорят, что задача находится в классе NP, если ее решение может быть проверено за полиномиальное время.

Учитывая ввод G = (V, E) и размер набора K , ответом являются два набора: I (независимый набор) и C (множество клики). Есть три шага, чтобы проверить решение этой проблемы:

  • Проверка независимого набора: для всех пар вершин (x, y) , таких что x, y ∈ I и (x, y) ∉ E . Это займет O(n 2 ) времени, поскольку | я | = К и K ≤ n, где n это количество вершин.
  • Проверка набора клик: для всех пар вершин (x, y) , таких что x, y ∈ C и (x, y) ∈ E . Это заняло бы время O(n 2 ) , поскольку |C| = К и К ≤ п где n — количество вершин.
  • Проверьте размер обоих наборов: Чтобы проверить |I| = |С| = к занимает O(1) раз.

Таким образом, проверка решения для Clique+IS занимает не более O(n 2 ) , что является полиномиальным по своей природе, поэтому Clique+IS принадлежит к классу NP .

2. Clique + IS — задача NP-Hard:

Теперь нам нужно показать, что Clique + IS по крайней мере так же сложна, как известная NP-полная задача, с помощью метода сокращения.

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

We are going to show the reduction from Clique -> Clique+IS. 

Однако также можно показать редукцию как Независимое множество -> Клика + ИС, где известно, что Независимое множество является NP-полной проблемой.

Преобразование ввода: нам нужно преобразовать ввод из Clique во ввод в Clique+IS.

Клика принимает входной граф G = (V, E) и параметр K для заданного размера. Чтобы преобразовать ввод из Clique в Clique+IS:

  • Мы создадим такой граф, как G'(V', E') , который будет копией данного графа G = (V, E) .
  • Мы собираемся добавить вершины независимого множества I к графу G'. такой, что | я | знак равно К и К ≤ п .

Итак, график G' будет граф, который будет иметь все вершины и ребра из графа G и вершины из независимого множества I .

Создание нового графа займет O(|n| + |m|) времени. Добавление новых вершин займет О(н) . Так как |я| = K и K ≤ n, где n — количество вершин, а m — ребер. Таким образом, преобразование входных данных может выполняться за полиномиальное время .

Выходное преобразование: нам нужно преобразовать решение Clique + IS в решение задачи Clique.

  • Решение Clique+IS дает множество C , которое представляет собой клику размера K , и набор I , который является независимым набором размера К.
  • Это решение можно преобразовать в решение проблемы клики, установив C как клику размера K для графа G .
  • Мы удалим вершины независимого множества I из графа G'(V', E') , что приведет к графу G (V, E) с кликой для G , равной клике для G', потому что между G и G нет разницы ребер. Г' .

Вершины можно отбросить за O(n) , так как | я | = К а также K ≤ n , где n — количество вершин, поэтому выходное преобразование может быть выполнено за полиномиальное время .

Корректность: Теперь нам нужно доказать правильность утверждения, в котором говорится, что «Решение клики + IS выходит тогда и только тогда, когда существует решение проблемы клики» .

  • Мы создали новый граф G'= (V', E') из графа G в задаче клики, который содержит все вершины и ребра из графа G , а также вершины из независимого множества I .
  • По сравнению с графом G в G' не добавлялось никаких дополнительных ребер.
  • Теперь, если клика C существует в графе G'(V', E') , она также будет существовать в графе G(V, E) , потому что единственная разница между G и G' состоит в вершинах из независимого множества I , которые не соединены никаким ребром и, следовательно, не будут частью множества клик C .
  • Это показывает, что если Clique+IS имеет решение, то Clique тоже будет, т.е. Clique+IS → Clique.

Кроме того, поскольку оба графа имеют одинаковые ребра, если в графе G'(V', E') нет клики, то клика в графе G(V, E) не может существовать. G' имеет лишние вершины из независимого множества I , но соединяющих их ребер нет. Это доказало, что если Clique+IS не имеет решения, то Clique также не имеет решения, т. е. ! Клика-IS → ! Клика (¬Clique-IS → ¬Clique) . Эта доказанная Clique + IS выходит, если существует решение проблемы Clique .

Вывод:

Hence, we can conclude that Clique+IS is an NP-complete problem.  

Для получения более подробной информации см.:
Проектирование и анализ алгоритмов.

РЕКОМЕНДУЕМЫЕ СТАТЬИ