Fundamental Problems on Bounded-Treewidth Graphs: The Real Source of Hardness

It is known for many algorithmic problems that if a tree decomposition of width t is given in the input, then the problem can be solved with exponential dependence on t. A line of research by Lokshtanov, Marx, and Saurabh [SODA 2011] produced lower bounds showing that in many cases known algorithms achieve the best possible exponential dependence on t, assuming the SETH. The main message of our paper is showing that the same lower bounds can be obtained in a more restricted setting: a graph consisting of a block of t vertices connected to components of constant size already has the same hardness as a general tree decomposition of width t. Formally, a (σ,δ)-hub is a set Q of vertices such that every component of Q has size at most σ and is adjacent to at most δ vertices of Q. bullet For every ε> 0, there are σ,δ> 0 such that Independent Set/Vertex Cover cannot be solved in time (2-ε)p· n, even if a (σ,δ)-hub of size p is given in the input, assuming the SETH. This matches the earlier tight lower bounds parameterized by the width of the tree decomposition. Similar tight bounds are obtained for Odd Cycle Transversal, Max Cut, q-Coloring, and edge/vertex deletions versions of q-Coloring. bullet For every ε>0, there are σ,δ> 0 such that Triangle-Partition cannot be solved in time (2-ε)p· n, even if a (σ,δ)-hub of size p is given in the input, assuming the Set Cover Conjecture (SCC). In fact, we prove that this statement is equivalent to the SCC, thus it is unlikely that this could be proved assuming the SETH. bullet For Dominating Set, we can prove a non-tight lower bound ruling out (2-ε)p· nO(1) algorithms, assuming either the SETH or the SCC, but this does not match the 3p· nO(1) upper bound.