Prouver Trouver des chemins K Disjoints à partir de n chemins donnés dans un graphique dirigé est NP-complet

Question

Problème: Donné n chemins dans un graphique dirigé g (v, e) et un entier K, découvrez des chemins K, tels que deux d'entre eux ne passent pas à travers un nœud ordinaire.

Prouvez que le problème donné est en NP-complet.

J'ai pu prouver que le problème est dans NP.Astuce est que nous devons trouver une réduction du temps polynomial du problème définitif indépendant à ce problème, prouve qu'il est dans NP-dur.

Answer 1

membres de votre problème dans $ \ mathsf {np} $ est trivial. Pour prouver que c'est aussi $ \ mathsf {np} $ -hard envisager une instance de (la version de décision de) ensemble indépendant consistant à un graphique $ g= (v, e) $ avec $ | v |= n $ et d'un entier $ K $ .

construire le graphique $ h= (v ', e') $ où $ v '= v \ tasse \ {x_ {u, v} \,: \, (u, v) \ in e \} $ et $ e '= v' \ fois v '$ < / span>.

pour chaque $ u \ in v $ let $ v_1, v_2, \ dots, v_h $ être les voisins de $ u $ in $ g $ et définir le chemin $ p_u=utiller u, x_ {u, v_1}, x_ {u, v_2}, \ dots, x_ {u, v_h} \ rangs $ in $ H $ . Laissez $ \ mathcal {p}={p_u \,: \, u \ in v \} $

.

.

Il existe un ensemble indépendant de taille au plus $ K $ in $ g $ , si et Seulement s'il y a un sous-ensemble $ \ mathcal {p} '$ avec $ | \ mathcal {p}' | \ LE K $ tel que les chemins dans $ \ mathcal {p} '$ sont paires verte-disjoint.

plus précisément, si $ s $ est un ensemble indépendant de $ g $ , alors $ \ {p_u \,: \, u \ in s \} $ est une collection de chemins paires vertex-disjoints dans $ h> $ h $ et, si $ \ mathcal {p} '$ est une collection de chemins de verx-disjoints paires dans $ H $ , puis $ \ {u \,: \, p_u \ in \ mathcal {p} '\} $ est un ensemble indépendant de < Span Classe="Math-Conteneur"> $ G $ .