Strong Backdoors to Bounded Treewidth SAT - todo314 @ ウィキ

Strong Backdoors to Bounded Treewidth SAT

• Serge Gaspers, Stefan Szeider
• In FOCS 2013

• サイズkのbackdoorの存在判定
  • FPT近似
• Backdoor
  • 現実の問題は多項式時間で解ける問題に近いんじゃね？
  • CNFにいくつか代入すると2CNF！
  • Pへの近さを計りたい
  • F=CNF
  • C={2CNF} 近づけたいCNF
  • B={x1,x2}
  • Bがbackdoor⇔∀T∈2^B, F[T]∈C
  • |B|≦kなBを探したい！！
• FPT
  • O(f(k)n^c)がほしい
  • FPT近似（下逆かも…）
    • サイズ2^k以下はが有る
    • サイズk以下は無い
• feedback vertex setとか考える

FOCS

2013-11-03 03:12:06 (Sun)