Доказать, что нахождение k непересекающихся путей от N Данные пути в направленном графике NP-Complete

Question

Проблема: Учитывая N Пути в направленном графе G (V, E) и целое число K, узнайте K Пути среди них такой, что никто из них не проходит через общий узел.

Докажете, что заданная проблема в NP-Clace.

Я смог доказать, что проблема в NP.Подсказка заключается в том, что нам нужно придумать многочлен сокращение времени независимой задачи на эту проблему, докажующуюся, что она находится в NP-Hard.

Answer 1

Членство в вашей проблеме в $ \ mathsf {NP} $ тривиально. Чтобы доказать, что это также $ \ MAMSF {NP} $ - считает экземпляр (решающую версию) независимого множества, состоящего из графика $ g= (v, e) $ с $ | v |= n $ и целочисленного $ k $ .

Построить график $ h= (v ', e') $ где $ v '= v \ Cup \ {x_ {u, v} \,: \, (u, v) \ в e \} $ и $ E '= V' \ RUS V '$ < / span>.

Для каждого $ u \ in v $ Пусть $ v_1, v_2, \ dots, v_h $ Будьте соседей $ u $ в $ g $ и определите путь $ p_u=langle u, x_ {u, v_1}, x_ {u, v_2}, \ dots, x_ {u, v_h} \ pangle $ в $ H $ . Пусть $ \ mathcal {p}={p_u \,: \, u \ in v \} $ .

Есть независимый набор размеров на большинстве $ k $ в $ G $ , если и Только если есть подмножество $ \ mathcal {p} '$ с $ | \ mathcal {p}' | \ le k $ такой, что пути в $ \ mathcal {p} '$ являются парапрепространными вершинами.

Точнее, если $ S $ - это независимый набор $ g $ , затем $ \ {p_u \,: \, u \ in s \} $ представляет собой коллекцию парных вершинных путей в $ H $ и, если $ \ mathcal {p} '$ - это коллекция парапорехозяйственных вершинных путей в $ H $ , затем $ \ {u \,: \, p_u \ in \ mathcal {p} '\} $ - независимый набор < Spant Class="Математический контейнер"> $ g $ .