Department of Applied Mathematics & Physics, Kyoto University

Technical Report 2014-005 (October 14, 2014)

Complexity and Kernels for Bipartition into Degree-bounded Induced Graphs
by Mingyu Xiao and Hiroshi Nagamochi

pdf File

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. First, we prove that the two problems are NP-complete with any nonnegative integers a and b except a=b=0. Second, we show the fixed- parameter tractability of constrained versions of these two problems with parameter k=|V_A| being the size of one part of the bipartition by deriving some problem kernels for them.