Complexity and kernels for bipartition into degree-bounded induced graphs

详细信息    查看全文

• 作者：Mingyu Xiao^a ; ^{myxiao@uestc.edu.cn} ; Hiroshi Nagamochi^b ; ^{nag@amp.i.kyoto-u.ac.jp}
• 关键词：Graph algorithms ; Bipartition ; Kernelization ; NP-hard ; Fixed-parameter tractable
• 刊名：Theoretical Computer Science
• 出版年：2017
• 出版时间：10 January 2017
• 年：2017
• 卷：659
• 期：Complete
• 页码：72-82
• 全文大小：457 K
• 卷排序：659

文摘

In this paper, we study the parameterized complexity of the problems of partitioning the vertex set of a graph into two parts VAVA and VBVB such that VAVA induces a graph with degree at most a (resp., an a  -regular graph) and VBVB 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=0a=b=0, the two problems become the polynomially solvable problem of checking the bipartition of a graph. When a=0a=0 and b=1b=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=0a=b=0. Secondly, we show the fixed-parameter tractability of these two problems with parameter k=|VA|k=|VA| being the size of one part of the bipartition by deriving several problem kernels for them and constrained versions of them.