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

Barış Can Esmer, Jacob Focke, Dániel Marx +1

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…