Known Algorithms on Graphs of Bounded Treewidth Are Probably Optimal
Daniel Lokshtanov, Dániel Marx, Saket Saurabh · ACM Transactions on Algorithms · 2018
We obtain a number of lower bounds on the running time of algorithms solving problems on graphs of bounded treewidth. We prove the results under the Strong Exponential Time Hypothesis of Impagliazzo and Paturi. In particular, assuming that n -variable m -clause SAT cannot be solved in time (2-ϵ) n m O (1) , we show that for any ϵ > 0: • I ndependent S et cannot be solved in time (2-ϵ) tw( G ) | V ( G )| O (1) , • D ominating S et cannot be solved in time (3-ϵ) tw( G ) | V ( G )| O (1) , • M ax C ut cannot be solved in time (2-ϵ) tw( G ) | V ( G )| O (1) , • O dd C ycle T ransversal cannot be solved in time (3-ϵ) tw( G ) | V ( G )| O (1) , • For any fixed q ≥ 3, q -C oloring cannot be solved in time ( q -ϵ) tw ( G ) | V ( G )| O (1) , • P artition I nto T riangles cannot be solved in time (2-ϵ) tw ( G ) | V ( G )| O (1) . Our lower bounds match the running times for the best known algorithms for the problems, up to the ϵ in the base.