Dimostrare la ricerca di k disgiunti i percorsi da n determinati percorsi in un grafico diretto è np-completo

Question

Problema: dato n Percorsi in un grafico diretto G (V, E) e un intero K, scopri i percorsi K tra loro tale che nessun due di loro passano attraverso un nodo comune.

Dimostra che il problema dato è in NP-Completo.

Sono stato in grado di dimostrare che il problema è in NP.Il suggerimento è che dobbiamo inventare una riduzione del tempo polinomiale del problema stabilito indipendente per questo problema dimostrare che è in NP-Hard.

Answer 1

Iscrizione del tuo problema in $ \ mathsf {np} $ è banale. Per dimostrare che è anche $ \ mathsf {np} $ -Hard considera un'istanza di (la versione decisionale di) set indipendente composto da un grafico $ G= (v, e) $ con $ | v |= n $ e di un intero $ k $ .

Costruisci il grafico $ h= (v ', e') $ dove $ v '= v \ tazza \ {x_ {u, v} \,: \, (u, v) \ in e \} $ e $ e '= v' \ volte v '$ < / span>.

per ogni $ u \ in V $ let $ v_1, v_2, \ dots, v_h $ essere i vicini di $ U $ in $ G $ e definisci il percorso $ P_U=Langle U, X_ {U, V_1}, X_ {U, V_2}, \ Dots, X_ {U, V_H}} Rangle $ in $ H $ . Let $ \ Mathcal {p}={p_u \,: \, u \ in v \ \} $ .

C'è un insieme indipendente di dimensioni al massimo $ k $ in $ G $ , se e Solo se c'è un sottoinsieme $ \ mathcal {p} '$ con $ | \ mathcal {p}' | \ Le k $ In tal modo i percorsi in $ \ mathcal {p} '$ sono a coppia vertice-disgiunta.

Più precisamente, se $ s $ è un set indipendente di $ G $ , quindi $ \ {p_u \,: \, u \ in s \} $ è una raccolta di percorsi a coppie di vertice-disgiunti in $ h $ e, se $ \ mathcal {p} '$ è una raccolta di percorsi di vertice-disgiunta a coppia in $ H $ , quindi $ \ {u \,: \, p_u \ in \ mathcal {p} '\} $ è un set indipendente di < Span Class="Math-Container"> $ G $ .