Докажите, что плотный подграф является NP-полным по обобщению.
Предпосылки: 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 для плотного подграфа таким образом, чтобы
- G' = G(V, Е)
- а = к
- б = (к * (к – 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
Для получения более подробной информации см.:
Проектирование и анализ алгоритмов.