Constrained domatic bipartition on trees

Given an undirected graph, the Constrained Domatic Bipartition Problem (CDBP) consists in determining a bipartition, if it exists, of the nodes into two dominating sets, with the additional constraint that one of the two subsets has a given cardinality. The problem is NP-hard in general and in this paper we focus on trees. First, we provide explicit solutions in simple cases, i.e., stars and paths. Then, we provide a polyhedral representation for all domatic bipartitions of a tree. Although the matrix associated with the polyhedron is not totally unimodular, we prove that all its vertices have integral components. Adding the cardinality constraint, the resulting polyhedron will generally lose this property. We then propose a constructive, dynamic programming algorithm for CDBP on trees, that is able to simultaneously find a solution for all possible cardinalities. The proposed algorithm is polynomial with complexity O(n3), where n is the number of nodes. Finally, we discuss the extension of CDBP to the weighted case, show that it is NP-hard and provide a pseudo-polynomial algorithm for the problem.