论文标题
反馈顶点集的近亲，而没有单指数算法，由TreeWidth参数
Close relatives of Feedback Vertex Set without single-exponential algorithms parameterized by treewidth
论文作者
论文摘要
剪切技术和基于等级的方法已导致单个指数FPT算法通过树宽参数（即，在时间$ 2^{o（tw）} n^{o（1）} $中运行，用于反馈顶点，用于经典图形问题的反馈顶点集合和连接的版本（例如Vertex Comparation of Pertex Coverx offex offex cover and Olimation and intertex and opartiate and opariated设置）。我们表明，子集反馈顶点集，子集奇数循环横向，受限的边缘 - 子集反馈边缘集，节点多路切割和多路切割不太可能具有这样的运行时间。 More precisely, we match algorithms running in time $2^{O(tw \log tw)}n^{O(1)}$ with tight lower bounds under the Exponential-Time Hypothesis (ETH), ruling out $2^{o(tw \log tw)}n^{O(1)}$, where $n$ is the number of vertices and $tw$ is the treewidth of the input graph.我们的算法扩展到加权情况，而我们的下限也适用于较大的参数路径，不需要权重。我们还表明，与奇数循环横向相反，没有$ 2^{o（tw \ log tw）} n^{o（1）} $ - 在ETH下均匀循环termersserm的时间算法。
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 running in time $2^{O(tw \log tw)}n^{O(1)}$ with tight lower bounds under the Exponential-Time Hypothesis (ETH), ruling out $2^{o(tw \log tw)}n^{O(1)}$, where $n$ is the number of vertices and $tw$ 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 $2^{o(tw \log tw)}n^{O(1)}$-time algorithm for Even Cycle Transversal under the ETH.
