Вопрос

Я пытаюсь понять эту проблему из Алгоритмы. С. Дасгупта, Ч. Пападимитриу и УФ -Вазирани, Глава8, Pg281. Проблема 8.19

А воздушный змей это график на равномерное количество вершин, скажем, $ 2n $, в котором $ n $ из вершин образуют клику, а оставшиеся вершины $ n $ подключены в «хвосте», который состоит из пути, соединенного с одним из Вершины клики. Учитывая график $ g $ и цель $ g $, проблема воздушного змея просит подграфа, который является воздушным змеем и содержит узлы $ 2G $. Докажите, что воздушный змей является NP-полным.

Есть указатели, чтобы начать с этой проблемы? Я полностью потерян с этим.

Это было полезно?

Решение

Вы можете уменьшить клику ($ g $, имеет клику размера $ k $) для воздушных змеев: Учитывая $ g = (v, e) $ и $ k $, просто постройте в полиномиальном времени новый график $ g '$ таким образом : Для каждого узла $ v_i $ добавьте хвост $ k $ новых узлов.

Если $ g '$ имеет воздушный змей размера 2K $, то у $ g $ есть клика размера $ k $ (змея без хвоста). Добавленные узлы не могут ввести новые клики на G ′, так что $ g $ содержит точно одинаковые клики $ g '$.

Лицензировано под: CC-BY-SA с атрибуция
Не связан с cs.stackexchange
scroll top