Minimum Bisection is Fixed Parameter Tractable
-
Marek Cygan, Daniel Lokshtanov, Marcin Pilipczuk, Michał Pilipczuk, Saket Saurabh
-
STOC 2014
-
minimum bisection
-
グラフを半分にするためには何本の辺を除けばいいか
-
k本取り除いて頂点集合AとBに分割される
-
||A|-|B||≦1
-
これがFPT!!
-
O(2^O(k^3)*n^3*log^3 n)
-
k: 解の大きさ
-
おおまかな流れ
-
木幅は制限しない
-
2つバッグの共通部分の大きさは2^O(k)
-
DP
-
状態数は2^O(k)n^2だけど
-
更新が木幅に関して指数になりそう
-
Hypergraph Paintingという問題(手法?)
STOC minimum bisection
2014-10-03 17:46:26 (Fri)
最終更新:2014年10月03日 17:46