Complexity and kernels for bipartition into degree-bounded induced graphs
Complexity and kernels for bipartition into degree-bounded induced graphs
复制标题
二分到有度诱导图的复杂性和内核
DOI：
10.1007/978-3-319-13075-0_34
复制
发表时间：
2017
期刊：
影响因子：
--
通讯作者：
Hiroshi Nagamochi
中科院分区：
文献类型：
--
作者：
Mingyu Xiao;Hiroshi Nagamochi
本文研究了将图的顶点集分成两部分，从而导出至多有度的图(A-正则图)和导出至多有度的图(A-正则图)问题的参数化复杂性。这两个问题分别称为上度有界二分问题和正则二分问题。首先，我们证明了这两个问题都是NP-完全的，且不含任何非负整数和概念。其次，我们证明了参数为二分划大小的两个问题对于固定整数是固定参数可处理的，或者通过推导它们的一些问题核来证明。
In this paper, we study the parameterized complexity of the problems of partitioning the vertex set of a graph into two partsandsuch thatinduces a graph with degree at most(resp., an-regular graph) andinduces a graph with degree at most(resp., a-regular graph). These two problems are calledUpper-Degree-Bounded BipartitionandRegular Bipartitionrespectively. First, we prove that the two problems are NP-complete with any nonnegative integersandexcept. Second, we show that the two problems with parameterbeing the size ofof a bipartitionare fixed-parameter tractable for fixed integerorby deriving some problem kernels for them.