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

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

Предпосылки: NP-полнота, NP-класс, плотный подграф

Задача : Дан граф G = (V, E) и два целых числа a и b . Множество таких вершин графа G , между которыми имеется не менее b ребер, называется плотным подграфом графа G.

Объяснение: Чтобы доказать проблему плотного подграфа как NP-полноту путем обобщения, мы собираемся доказать, что она является обобщением известной NP-полной проблемы. В этом случае мы собираемся взять Clique как известную проблему, которая, как уже известно, является NP-полной и объяснена в Доказательстве того, что клика является NP-полной, и нам нужно показать сокращение от Clique → Dense Subgraph.

Clique is a subset of vertices of an undirected graph such that every two distinct vertices in the clique are adjacent.

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

1. Преобразование входных данных: нам нужно преобразовать входные данные из Clique во входные данные плотного подграфа.

Clique Input:  An undirected graph G(V, E) and integer k.
Dense Subgraph Input : An undirected graph G"(V, E) and two integers a and b.

Мы собираемся преобразовать ввод из Clique для плотного подграфа таким образом, чтобы

  1. G' = G(V, Е)
  2. а = к
  3. б = (к * (к – 1))/2

Это преобразование займет O (1) раз, поэтому он полиномиален по своей природе.

2. Преобразование вывода: нам нужно преобразовать решение из плотного графа в решение задачи клики.

Решение плотного графа приведет к набору a, который будет кликой размера k . как к = а . Таким образом, Clique может использовать прямой вывод из Dense Graph. Поскольку преобразование не требуется, оно снова имеет полиномиальный характер .

3. Корректность: мы ограничили диапазон входного значения b таким образом, что (k¦2) со значением как (k * (k – 1))/2 .

Теперь ищем подграф, имеющий k вершин и соединенный не менее чем (k * (k – 1))/2 ребрами.

  • Поскольку в полном графе n вершин могут иметь не более (n * (n – 1))/2 ребер между ними, мы можем сказать, что нам нужно найти подграф из k вершин, которые имеют ровно ( k * (k – 1 ))/2 ребер, что означает, что выходной граф должен иметь ребро между каждой парой вершин, которое представляет собой не что иное, как клику из k вершин.
  • Точно так же клика k вершины на графе G(V, E) должны иметь (k * (k – 1))/2 ребер, который является не чем иным, как плотным подграфом графа G (V, E)

Итак, это означает, что Dense-Subgraph имеет решение Clique имеет решение.
Полная редукция занимает полиномиальное время , а клика является NP-полной, поэтому плотный подграф также является NP-полной.

Вывод:

Hence we can conclude that Dense-Subgraph is NP Complete
 

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

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