Complexity and kernels for bipartition into degree-bounded induced graphs
Complexity and kernels for bipartition into degree-bounded induced graphs
复制标题
二分到有度有界诱导图的复杂性和内核
DOI：
10.1016/j.tcs.2016.11.011
复制
发表时间：
2014-12
影响因子：
1.1
通讯作者：
Hiroshi Nagamochi
中科院分区：
文献类型：
--
作者：
Mingyu Xiao;Hiroshi Nagamochi
在本文中，我们研究了将图的顶点集划分为两部分 V A 和 V B 问题的参数化复杂性，使得 V A 归纳出度数最多为 a 的图（分别为 a 正则图），而 V B 归纳出度数最多为 b 的图（分别为 b 正则图）。这两个问题分别称为上界二分问题和正则二分问题。当a=b=0时，这两个问题就成为检查图二分性的多项式可解问题。当a= 0且b= 1时，正则二分成为众所周知的NP难题，称为支配诱导匹配。在本文中，首先我们证明这两个问题对于除a= b= 0之外的任何非负整数a和b都是NP完全的。其次，我们证明了参数k=|时这两个问题的固定参数可处理性。 VA|通过为它们派生几个问题内核及其约束版本，得到二分区一部分的大小。
In this paper, we study the parameterized complexity of the problems of partitioning the vertex set of a graph into two parts V A and V B such that V A induces a graph with degree at most a (resp., an a-regular graph) and V B induces a graph with degree at most b (resp., a b-regular graph). These two problems are called Upper-Degree-Bounded Bipartition and Regular Bipartition, respectively. When a= b= 0, the two problems become the polynomially solvable problem of checking the bipartition of a graph. When a= 0 and b= 1, Regular Bipartition becomes a well-known NP-hard problem, called Dominating Induced Matching. In this paper, firstly we prove that the two problems are NP-complete with any nonnegative integers a and b except a= b= 0. Secondly, we show the fixed-parameter tractability of these two problems with parameter k=| V A| being the size of one part of the bipartition by deriving several problem kernels for them and constrained versions of them.
登录
查看更多内容
DOI：
10.1007/978-3-642-45030-3_52
发表时间：
2013-02
期刊：
ArXiv
影响因子：
--
作者：
Min Chih Lin;Michel J. Mizrahi;J. Szwarcfiter
通讯作者：
Min Chih Lin;Michel J. Mizrahi;J. Szwarcfiter
DOI：
10.1002/(sici)1097-0118(199611)23:3
发表时间：
1996-11
期刊：
J. Graph Theory
影响因子：
--
作者：
O. Borodin
通讯作者：
O. Borodin
DOI：
10.1016/j.dam.2006.10.005
发表时间：
2007-04
期刊：
Discret. Appl. Math.
影响因子：
--
作者：
C. Bazgan;Z. Tuza;D. Vanderpooten
通讯作者：
C. Bazgan;Z. Tuza;D. Vanderpooten
DOI：
10.1007/978-3-540-24587-2_46
发表时间：
2003-12
期刊：
--
影响因子：
--
作者：
C. Bazgan;Z. Tuza;D. Vanderpooten
通讯作者：
C. Bazgan;Z. Tuza;D. Vanderpooten
DOI：
10.1016/0196-6774(84)90032-4
发表时间：
1982
期刊：
J. Algorithms
影响因子：
--
作者：
David S. Johnson
通讯作者：
David S. Johnson