Strong computational lower bounds via parameterized complexity

Jianer Chen, Xiuzhen Huang, Iyad A. Kanj and Ge Xia
Journal of Computer and System Sciences
Volume 72, Issue 8 , December 2006, Pages 1346-1367
http://dx.doi.org/10.1016/j.jcss.2006.04.007

STOC2004論文のジャーナル版．
次のような結果を示している．

• 与えられたグラフに大きさkの支配集合 (dominating set) があるかどうか問う問題を考える．彼らはW[1]=FPTでなければ，この問題に対するf(k)n^{o(k)}m^{O(1)}時間アルゴリズムが任意のfに対して存在しないことを示した．ただし，nはグラフの頂点数，mはグラフの辺数である．

この「任意のf」という部分はとても重要である．

• 与えられたグラフに大きさkのクリークが存在するかどうか問う問題を考える．彼らはSNPがSUBEXPに含まれないならば，この問題を解くf(k)m^{o(k)}時間アルゴリズムが任意のfに対して存在しないことを示した．

道具として「linear fpt-reduction」という概念を新たに提案し，うまく使っている．