Parameterized complexity of three edge contraction problems with degree constraints
Parameterized complexity of three edge contraction problems with degree constraints
复制标题
DOI：
10.1007/s00236-014-0204-z
复制
发表时间：
2014-08
期刊：
影响因子：
0.6
通讯作者：
R. Belmonte;P. Golovach;P. Hof;D. Paulusma
中科院分区：
文献类型：
--
作者：
R. Belmonte;P. Golovach;P. Hof;D. Paulusma
对于任何图类，收缩问题需要作为输入一个图和一个整数，并询问是否存在一个图，这样可以修改，在使用最多边收缩。我们研究了三种不同类型的-压缩图的参数化复杂性：最大度图类，正则图类和-退化图类。我们完全分类的参数化复杂性的所有三个问题的参数，和。此外，我们表明，收缩承认一个顶点核的连通图时，而问题是困难的，当类退化图，因此预计不承认一个核。特别地，我们的结果意味着-压缩允许一个线性顶点核时，是类的循环。
For any graph class, the-Contractionproblem takes as input a graphand an integer, and asks whether there exists a graphsuch thatcan be modified intousing at mostedge contractions. We study the parameterized complexity of-Contractionfor three different classes: the classof graphs with maximum degree at most, the classof-regular graphs, and the class of-degenerate graphs. We completely classify the parameterized complexity of all three problems with respect to the parameters,, and. Moreover, we show that-Contractionadmits anvertex kernel on connected graphs when, while the problem is-hard whenis the class of-degenerate graphs and hence is expected not to admit a kernel at all. In particular, our results imply that-Contractionadmits a linear vertex kernel whenis the class of cycles.