Complexity and kernels for bipartition into degree-bounded induced graphs

In this paper, we study the parameterized complexity of the problems of partitioning the vertex set of a graph into two parts VA and VB such that VA induces a graph with degree at most a (resp., an a-regular graph) and VB 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=|VA| being the size of one part of the bipartition by deriving several problem kernels for them and constrained versions of them.