activity
20222026
most citedParameterized Complexity of Weighted Multicut in Trees

1 citations · 1 across the 1 of their papers we have counts for

collaborators
Showing 2023Show all

1 paper · 1 filter

cs.CC2023

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…