計算包含循環的有向圖中的簡單路徑的數量

Question

我有興趣計算圖中兩個節點之間的簡單路徑（無節點重複）的總數（稀疏，有向和包含週期）。該圖是一個強連通的組件。

我最初嘗試使用矩陣乘法，其中我把鄰接矩陣提升到從2到n-1的所有冪，n是節點的數量。但是由於圖中的循環，這失敗了。對於一個DAG，只要計算所有這些權力並總結出來就可以完成這項工作。

Answer 1

這個問題沒有有效的算法。

從頂點倒數了的簡單路徑的數量的問題到噸是＃P-完整。因此，你不能指望通用的多項式時間算法。參見例如，https://cstheory.stackexchange.com/q/20246/5038,https://stackoverflow.com/a/5570751/781723，https://cs.stackexchange.com/q/423/755。

有時間試圖找到一些方法來避免解決這個問題，或者做一個近似算法或什麼。

Answer 2

不幸的是，這個問題在任意圖上是非常不平凡的。有一種分析方法，但它需要明確的計算，因此不能提供通用答案。它包括加權每個邊由一個變量x_node離開一個節點。然後考慮這些變量彼此通勤並且平方爲零。如此加權的鄰接矩陣的冪生成簡單的路徑。這個鄰接矩陣被稱爲圖的冪零鄰接矩陣，變量存在於Clifford代數中（參見R. Schott的文獻）。正如我前面提到的，這種方法不幸在很大的圖上是無用的，因爲它需要分析計算實際的矩陣功率。我希望在這一點上被證明是錯誤的。