Minimum Bisection is Fixed Parameter Tractable

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: 解の大きさ
  • おおまかな流れ
    • 専用の木分解→DP!!
  • 分割
    • A∪B = V
    • E(A\B, B\A) = φ
  • 木幅は制限しない
  • 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