On the Parameterized Complexity of Cutting a Few Vertices from a Graph
On the Parameterized Complexity of Cutting a Few Vertices from a Graph
复制标题
关于从图中切割几个顶点的参数化复杂性
DOI：
10.1007/978-3-642-40313-2_38
复制
发表时间：
2013
期刊：
影响因子：
--
通讯作者：
Janne H. Korhonen
中科院分区：
文献类型：
--
作者：
F. Fomin;P. Golovach;Janne H. Korhonen
研究了用一个小的顶点分离器从图中分离一小部分顶点的参数化复杂性。也就是说，给定图G和整数k，t，任务是找到一个顶点集X，|X| ≤ k且|N（X）|≤ t。我们证明了
当用t参数化时，该问题是固定参数易处理的（FPT），但当用k参数化时，该问题是W[1]-难的，且
问题的终端变体，其中X必须包含给定的顶点s，当仅由k或t参数化时是W[1]-困难的，但当由k + t参数化时是FPT的。
我们还表明，如果我们考虑边割，而不是顶点割，终端变体是NP-难的。
We study the parameterized complexity of separating a small set of vertices from a graph by a small vertex-separator. That is, given a graph G and integers k, t, the task is to find a vertex set X with |X| ≤ k and |N(X)| ≤ t. We show that
the problem is fixed-parameter tractable (FPT) when parameterized by t but W[1]-hard when parameterized by k, and
a terminal variant of the problem, where X must contain a given vertex s, is W[1]-hard when parameterized either by k or by t alone, but is FPT when parameterized by k + t.
We also show that if we consider edge cuts instead of vertex cuts, the terminal variant is NP-hard.