  We consider a bipartite version of the color degree matrix problem. A
bipartite graph $G(U,V,E)$ is half-regular if all vertices in $U$ have the same
degree. We give necessary and sufficient conditions for a bipartite degree
matrix (also known as demand matrix) to be the color degree matrix of an
edge-disjoint union of half-regular graphs. We also give necessary and
sufficient perturbations to transform realizations of a half-regular degree
matrix into each other. Based on these perturbations, a Markov chain Monte
Carlo method is designed in which the inverse of the acceptance ratios are
polynomial bounded.
  Realizations of a half-regular degree matrix are generalizations of Latin
squares, and they also appear in applied neuroscience.
