Problems in NP can Admit Double-Exponential Lower Bounds when Parameterized by Treewidth or Vertex Cover

Florent Foucaud, Esther Galby, Liana Khazaliya +4

Treewidth (tw) is an important parameter that, when bounded, yields tractability for many problems. For example, graph problems expressible in Monadic Second Order (MSO) logic and…