Algorithmic Lower Bounds for Problems Parameterized with Clique-Width

Many NP-hard problems can be solved efficiently when the input is restricted to graphs of bounded tree-width or clique-width. In particular, by the celebrated result of Courcelle, every decision problem expressible in monadic second order logic is fixed parameter tractable when parameterized by the tree-width of the input graph. On the other hand if we restrict ourselves to graphs of clique-width at most t, then there are many natural problems for which the running time of the best known algorithms is of the form n f ( t ), where n is the input length and f is some function. It was an open question whether natural problems like Graph C oloring, M ax -C ut, E dge D ominating S et, and H amiltonian P ath are fixed parameter tractable when parameterized by the clique-width of the input graph. As a first step toward obtaining lower bounds for clique-width parameterizations, in [ SODA 2009 ], we showed that unless FPT≠W[1], there is no algorithm with run time O ( g ( t ) · n c ), for some function g and a constant c not depending on t, for G raph C oloring, E dge D ominating S et and H amiltonian P ath. But the lower bounds obtained in [ SODA 2009 ] are weak when compared to the upper bounds on the time complexity of the known algorithms for these problems when parameterized by the clique-width. In this paper, we obtain the asymptotically tight bounds for M ax -C ut and E dge D ominating S et by showing that both problems cannot be solved in time f ( t ) n o ( t ), unless Exponential Time Hypothesis (ETH) collapses; and can be solved in time n O ( t ), where f is an arbitrary function of t, on input of size n and clique-width at most t. We obtain our lower bounds by giving non-trivial structure-preserving “linear FPT reductions”.

Authors

• Fedor V. Fomin
• Petr A. Golovach
• Daniel Lokshtanov
• Saket Saurabh 0001

Keywords

No keywords are indexed for this paper.