NP-полное доказательство от задачи Dasgupta на Kite
-
16-10-2019 - |
Вопрос
Я пытаюсь понять эту проблему из Алгоритмы. С. Дасгупта, Ч. Пападимитриу и УФ -Вазирани, Глава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 '$.