Beweisen Sie, dass K-Disjoint-Wege von n gegebenen Pfaden in einem gerichteten Graphen gefunden werden, ist NP-Complete

Question

Problem: Bei n-Pfaden in einem gerichteten Graph g (V, E) und einer Ganzzahl k, erfahren Sie K-Wege unter ihnen, so dass keine zwei von ihnen einen gemeinsamen Knoten passieren.

Beweisen Sie, dass das angegebene Problem in NP-komplett ist.

Ich konnte nachweisen, dass das Problem in NP ist.Hinweis ist, dass wir eine Polynom-Zeit-Reduktion des unabhängigen Set-Problems auf dieses Problem finden müssen, beweisen, dass es sich in NP-Hard befindet.

Answer 1

Mitgliedschaft Ihres Problems in $ \ Mathsf {NP} $ ist trivial. Um zu beweisen, dass es auch $ \ Mathsf {NP} $ -hard ist, berücksichtigen Sie eine Instanz von (der Entscheidungsversion von) unabhängigen Set, das aus einem Diagramm $ g= (V, E) $ mit $ | v |= n $ und einer Ganzzahl $ K $ .

Konstruieren Sie das Diagramm $ H= (V ', E') $ wo $ V '= v \ cup \ {x_ {u, v} \,: \, (u, v) \ in E \} $ und $ e '= v' \ times v '$ < / span>.

für jeden $ u \ in V $ Lassen Sie $ v_1, v_2, \ dots, v_h $ Seien Sie die Nachbarn von $ u $ in $ g $ und definieren Sie den Pfad $ P_U=Langle u, x_ {u, v_1}, x_ {u, v_2}, \ dots, x_ {u, v_h} \ Rangle $ in $ H $ . Lassen Sie $ \ Mathcal {P}={p_u \,: \, u \ in v \} $ .

Es gibt einen unabhängigen Größensatz in den meisten $ K $ in $ g $ , falls und Nur wenn es eine Subset $ \ Mathcal {P} gibt, '$ mit $ | \ mathcal {p}' | \ le k $ so, dass die Pfade in $ \ matcal {p} '$ paarweise vertex-disjunkt sind.

Genauer gesagt, wenn $ s $ ein unabhängiger Satz von $ G $ ist, dann $ \ {p_u \,: \, u \ in s \} $ ist eine Sammlung von paarweise vertex-disjunkten Pfaden in $ h $ und wenn $ \ matcal {p} '$ ist eine Sammlung von paarweise vertex-disjunkten Pfaden in $ H $ , dann $ \ {u \,: \, p_u \ in \ matcal {p} '\ \ \ \ matcal {p}' \} $ ist ein unabhängiger Satz von < Span-Klasse="Math-Container"> $ g $ .