我想出來了！
先把 cap-free 跟 triangle-free 的 structure 弄好，
重要的觀察：wheels in triangle-free cleaned graphs are cutsets!
透過 tracking 穿過 decompositions，
然後再對 extended line tree 作量身打造的 O(n+m) algorithm，
就完成了！
hope that everything is correct:]
--
Woops, 時間計算有點錯誤，
decomposition 也要乘上 O(mn)!!
這樣最多可能要到O(n^8)...
除非 2-join 可以處理？
沒有留言:
張貼留言