subquadratic時間有向圖中的雙向生成樹

Question

這是我試圖解決的問題。給定一個有向圖G，它包含一個連接的子圖是：

• 包含選自G的每個節點
• 是無環
• 可通過除去任一個邊緣
• 斷開已每個源之間的路徑節點和每個匯節點

直觀上，我正在尋找的子圖包含一個向下指向和一個向上指向的樹，它們共享相同的根，並跨越G.我將它稱爲雙向onal生成樹問題，但它可能有另一個名稱。

我想過的愚蠢算法是循環遍歷圖中的每個節點，在該節點處開始向後和向前的DFS，然後連接搜索樹。如果存在雙向生成樹，我很肯定這會在某個迭代中找到一個。但是，它運行在O（V（V + E））時間。我的直覺是應該有一個更快的算法。我對麼？

Answer 1

警告：此答案不完整;此處的算法在某些情況下返回「未知」。我只是因爲沒有其他人在過去幾天提出過任何答案，而且它仍然是對問題本身的提案的改進，即將每個頂點作爲候選根，執行「向後的DFS」並且「前向DFS」（其中「前向DFS」不允許訪問由「後向DFS」訪問的任何節點），並確保所有頂點都被其中一個或另一個發現。

具體來說，有兩種方式下面的答案提高了你的建議：

• 正如你在你的問題請注意，您的建議要求Ø（V＆middot;（V   +   E））時間。以下答案只需要O（V   +   E）時間。
• 如果有向圖包含循環，則您的提議可能無法檢測到其頂點是此類循環的元素的雙向生成樹。因此，您的提案可能會虛假地返回「失敗」。下面的答案從不虛假地返回「失敗」，但是（如上所述）在某些情況下返回「未知」。

---

開始。 。 。如果ģ是無環的，那麼我們就可以決定在Ö（V   +   È）時間是否存在雙向生成樹，並且如果是這樣構造它在一個進一步Ô（V   +   E）時間。要知道爲什麼，請注意以下幾點：

• 如果有在v根的雙向生成樹，那麼這意味着對於每個頂點瓦特，還有無論是從v到路徑w，反之亦然。

• 如果我們有頂點的topological ordering（我們可以在構造Ö（V   +   È）時間），那麼對於任何給定的頂點v和瓦特，有肯定沒有路徑從對到對如果W優先於對在拓撲排序，反之亦然。

• 這意味着，我們可以發現頂點（如果有的話）具有路徑由拓撲排序有向圖，然後做兩個通行證或其他頂點：

  • 首先，我們遍歷頂點按照順序排列。我們希望找到所有「後向根」，意思是可以從它們的所有前輩可達到的頂點—，或者換句話說，我們想要消除任何頂點，其中而不是可以從某個前任可到達的頂點。爲此，請保留已經遇到的頂點的集合。當我們迭代時，我們刪除任何具有指向當前頂點的邊的頂點。只要這個集合是空的，當前頂點就是一個「後向根」。 （這是一個有點棘手，要做到這一點迭代嚴格Ø（V   +   Ë）的時間，但它是可行的，關鍵的見解是，我們需要存儲入站邊的列表中爲每個頂點，這可能需要ø（V   +   è）預處理通，如果這是不是最初我們的圖形表示的一部分。）
  • 然後，我們做反向，遍歷以相反的順序的頂點找到所有「前鋒」。

  頂點是一些雙向的生成樹，當且僅當這既是一個「前進根」和「向後根」的根源。一旦我們找到了這樣一個根，我們就可以通過從該根執行「前向DFS」和「反向DFS」來構建樹本身。

一個重要的特殊情況（其重要性將在下文中變得清晰）的情況是，兩個連續的頂點（「連續」在拓撲排序，我的意思）是都有效的根。在這種情況下，我們可以做從第一一個和「向前DFS」「反向DFS」從秒一個建立一個雙向生成樹，其中每個頂點有任一入度 ≤  1或出度  ≤  1.

---

OK，但如果摹包含一個週期？在這種情況下，您提出的算法永遠不會返回「失敗」，但只要根本身不是一個循環的一部分，至少可以保證找到一個雙向生成樹，即G。前面的部分完全忽略了這種情況。

要開始尋址這種情況下，請注意，我們可以使用Tarjan's algorithm，這需要ø（V   +   È）時間，以得到強連接部件的向無環圖ģ' G。 （如果ģ已經無環的，然後ģ'。  =   ģ）

要知道爲什麼ģ'是有用的，注意以下事項：

• 如果ģ具有根植於頂點的雙向生成樹v，則G'具有雙向spanni ng樹植根於代表強連通組件的頂點，該組件包含v。

  • 我承認，這個說法並不完全明顯。畢竟，有可能G具有雙向生成樹，其具有「穿過」單個強連接組件的多個分支，使得組件的總體indegree和outdegree均爲 >  >。但是，在這種情況下一個案例，我們可以通過移除其中一個產生的出站邊（如果我們位於根的「sourceward」一側）或入站邊（如果我們位於「入口邊」），我們總是可以「修復」G'向下「方）。

• 鑑於任何強連通有向圖^h和v在^h任何頂點，我們可以做的「前進DFS」或「反向DFS」出從v找到跨越樹H並且分別具有v作爲其唯一來源或其唯一接收器。因此，如果ħ是ģ的強連接部件中的一個，和ģ'具有雙向生成樹在表示ħ頂點具有任一入度 ≤  1或出度 ≤  1，那麼我們可以直接（並且有效地）構造一個子圖H，它是相應的雙向生成樹G的子圖，只要其餘的G的強連通組件也合作。

那麼剩下的唯一問題是與根的雙向生成樹摹的「：只是因爲它的一個雙向生成樹摹的根」，即並不一定意味着對應的強連接組件G包含任何雙向生成樹的根，其中包括G。例如，考慮該曲線圖中：

A B 
↓ ↓ 
C ↔ D 
↓ ↓ 
E F 

該圖沒有任何雙向生成樹，但強連通分量的相應的圖形確實（與對應於{C，  d}根） 。

---

所以，換句話說，我們有如下算法：

• 使用的Tarjan的算法來推導向無環圖的G 摹強連通分量的「。
• 拓撲分類G'並通過G'識別雙向生成樹的所有有效根。
• 如果沒有這樣的有效根，返回「失敗」。
• 如果在拓撲排序中有任何兩個相鄰的有效根，則返回「success」。 G必須包含從一個有效根中的某個頂點到另一個有效根中的某個頂點的邊緣vw;我們可以通過從v加上邊緣vw做「反向DFS」，再加上從w做「正向DFS」來獲得雙向生成樹。
• 如果有任何有效的根對應於只是單個頂點G的強連接組件，則返回「成功」。我們可以通過「向後的DFS」加上「向前的DFS」來獲得這個單一頂點，它是一個雙向生成樹G的根。
• 否則。 。 。返回「未知」。在這種情況下，我們可能會遇到一個小得多的問題：理論上，對於與某些強連接組件對應的每個有效根，我們需要檢查H以查看它是否具有適合於兩個方向的生成樹的入站和出站連接。但即使那個小得多的問題仍然涉及潛在的大量可能性，所以窮舉搜索似乎不可行。

所以，我在開始時提到的，這種算法需要Ø（V   +   Ë）的時間，它確定性在所有情況下返回樹或「失敗」在您的提案是確定性的加某些情況下，您的建議是不確定的;但仍然有一些情況下這種算法踢。 ： -/