ALMOST OPTIMAL LOWER BOUNDS FOR PROBLEMS PARAMETERIZED BY CLIQUE-WIDTH

作者：Fomin Fedor V^*; Golovach Petr A; Lokshtanov Daniel; Saurabh Saket

来源：SIAM Journal on Computing, 2014, 43(5): 1541-1563.

DOI：10.1137/130910932

• exponential time hypothesis
• clique-width
• max-cut
• edge dominating set

We obtain asymptotically tight algorithmic bounds for MAX-CUT and EDGE DOMINATING SET problems on graphs of bounded clique-width. We show that on an n-vertex graph of clique-width t both problems (1) cannot be solved in time f(t) n(o(t)) for any function f of t unless exponential time hypothesis fails, and (2) can be solved in time n(O(t)).

• 出版日期2014