Close relatives of feedback vertex set without single-exponential algorithms parameterized by treewidth
arXiv preprint arXiv:2007.14179, 2020•arxiv.org
The Cut & Count technique and the rank-based approach have lead to single-exponential
FPT algorithms parameterized by treewidth, that is, running in time $2^{O (tw)} n^{O (1)} $,
for Feedback Vertex Set and connected versions of the classical graph problems (such as
Vertex Cover and Dominating Set). We show that Subset Feedback Vertex Set, Subset Odd
Cycle Transversal, Restricted Edge-Subset Feedback Edge Set, Node Multiway Cut, and
Multiway Cut are unlikely to have such running times. More precisely, we match algorithms …
FPT algorithms parameterized by treewidth, that is, running in time $2^{O (tw)} n^{O (1)} $,
for Feedback Vertex Set and connected versions of the classical graph problems (such as
Vertex Cover and Dominating Set). We show that Subset Feedback Vertex Set, Subset Odd
Cycle Transversal, Restricted Edge-Subset Feedback Edge Set, Node Multiway Cut, and
Multiway Cut are unlikely to have such running times. More precisely, we match algorithms …
The Cut & Count technique and the rank-based approach have lead to single-exponential FPT algorithms parameterized by treewidth, that is, running in time , for Feedback Vertex Set and connected versions of the classical graph problems (such as Vertex Cover and Dominating Set). We show that Subset Feedback Vertex Set, Subset Odd Cycle Transversal, Restricted Edge-Subset Feedback Edge Set, Node Multiway Cut, and Multiway Cut are unlikely to have such running times. More precisely, we match algorithms running in time with tight lower bounds under the Exponential-Time Hypothesis (ETH), ruling out , where is the number of vertices and is the treewidth of the input graph. Our algorithms extend to the weighted case, while our lower bounds also hold for the larger parameter pathwidth and do not require weights. We also show that, in contrast to Odd Cycle Transversal, there is no -time algorithm for Even Cycle Transversal under the ETH.
arxiv.org