[問題] 找四環有幾個，有沒有比O(n^3)快的算法

[rareone (拍玄)]

四環（4-cycle）
在圖上我們稱他<a,b,c,d,a>使得四個點a,b,c,d依序相鄰

我想問問大神存不存在比O(n^3)還快地找四環計數算法
算出一張simple graph上有幾個4-cycle
拜託了>_< 我想過judge


--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 140.114.207.24
※ 文章網址: https://www.ptt.cc/bbs/Prob_Solve/M.1503418629.A.400.html
推 hcsoso: 無向圖嗎? 有 O(n^2) 的算法
→ hcsoso: 對每個點 x, 以及每對 x 的鄰居 (y,z), A[y,z]++
→ hcsoso: 最後檢查有沒有某個 A[u,v] 的值大於 1
推 hcsoso: 如果圖的邊數不多的話有更外的算法
推 hcsoso: http://www.tau.ac.il/~nogaa/PDFS/ayz4.pdf O(m^{4/3})
→ hcsoso: *快
推 hcsoso: 抱歉，上面的算法應改進成一發現某格值已為 1 而要加為 2
→ hcsoso:  時就要停下
→ hcsoso: 不然最糟時會是 O(n^3)...
→ rareone: 謝謝H大的回覆 我花點時間啃一下論文
推 FRAXIS: 我之前有想過一個 O(n^2) 時間 O(n) 空間的方法
→ FRAXIS: 不過只能偵測 4-cycle 存在而不是 counting
→ FRAXIS: 從每個點作 BFS ，如果鄰居的鄰居有交集就是有4-cycle
→ FRAXIS: 因為判斷鄰居的鄰居的交集頂多使用 O(n) 空間
→ FRAXIS: 所以總共的時間複雜度是O(n^2) 空間複雜度是O(n)
推 hcsoso: 哎呀我沒有意識到原 po 需要的是計數不是存在性…上面的
→ hcsoso: 推文是存在與否的算法
推 hcsoso: 另外請問 a,c 或 b,d 可相同嗎？
推 FRAXIS: 但是論文可以解 counting 吧 雖然需要矩陣乘法
推 hcsoso: 我指的是連結前面的那個
→ rareone: 了解 所以只需要要快一點的矩陣乘法就可以壓下去
推 firejox: 用矩陣乘法就算的出來了