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