查找從源到目標的頂點不相交路徑

是否有確定性算法來檢查圖形是否包含從源到目標的頂點不相交路徑，複雜度爲O(nm^2)（n是頂點數，m是邊數）或者這是NP-Hard（如果是這樣，爲什麼）？頂點不相交路徑是指沒有公共內部頂點的路徑。例如。查找從源到目標的頂點不相交路徑

s -> a -> b -> c -> d 
s -> x -> y -> z -> d

是頂點不相交，但

s -> a -> b -> c -> d 
s -> x -> a -> z -> d 
     ^

是不是因爲是公共頂點。

完整的問題是：

enter image description here

來源

2013-05-01 Jiew Meng

爲什麼我覺得這是作業？ – 2013-05-01 04:34:25

這個問題有點奇怪。 O（n * m^2）和NP-hard之間有相當的距離。鑑於這樣一個特定的複雜性目標，我懷疑你應該在「是」分支上工作。 :) – 2013-05-01 04:35:10

@TimothyShields，它的功課，或者說，它是我嘗試過去一年的考試試卷。 – 2013-05-01 10:27:21

的問題（在問問題，找「ONE」頂點s和t這是張貼問題的圖片不同之間不相交的路徑）是不NP-hard並且可以在多項式時間O(V^2E)來解決。此外，is there are k disjoint paths between s and t的問題也是而不是NP-Complete。

這是上面提到證明NP-completeness（http://www.shannarasite.org/kb/kbse48.html）的文章有一個微妙的差異....有你不知道的s和t，因此問題就變得很難。但是，一旦修復s和t，它就是多項式。

這裏是要找到在多項式時間a頂點不相交路徑算法---

轉換這個問題的最大流問題和使用Dinic's算法來解決它在O(V^2E) http://en.wikipedia.org/wiki/Dinitz_blocking_flow_algorithm

這是轉換：

選擇源s和目標t要在其間找到不相交路徑的頂點。對於每個頂點v添加兩個新頂點到G'（我們正在構建的圖），即對於每個v \in G添加v_1 and v_2到G'。

對於每個邊緣(a,b)添加以下邊緣(a_1, a_2)，(b_1, b_2)，(a_2, b_1)和(b_2, a_1)（記住，頂點已經被變換，並注意邊緣的方向上）。

添加S和T到G'和邊緣(S,s_1)和(t_2, T)。

爲所有邊緣指定權重1並運行最大流算法（在S和T之間）。如果您獲得1的最大流量，那麼該流（或路徑）對應於原始圖中的頂點不相交路徑。

我們那種k分離路徑：

的k的邊緣(S,s_1)，(t_2, T)，(s1_, s_2)和(t_1, t_2) .....和重量1對於其餘邊緣分配權重...運行迪尼奇的算法中再次，如果有最大流量的容量k，那給你不相交的路徑。

來源

2013-05-07 03:22:03 Bill

的問題是NP難問題。這可以通過從3-SAT減少來證明。 Here是一個證明的草圖。

分配n源/目標對（對於每個變量）。連接每對具有兩個路徑，每個具有'm'個內部節點（對於'm'個子句）。一種途徑是當變量爲'真'時，另一種'假'。

還分配'm'源/目標對（對於每個子句）。每條路徑連接3條路徑，每條路徑 - 通過相應的「變量」路徑的內部節點，如果該變量被否定或者不在條款中，則選擇「真」或「假」路徑。

然後找到'm + n'頂點不相交的路徑來解決3-SAT。

來源

2013-05-01 18:24:35

謝謝你:) – Agostino 2016-03-22 21:28:18

查找從源到目標的頂點不相交路徑

回答

相關問題