Partitioning the edge set of a bipartite graph into chain packings: complexity of some variations

An extension of the decomposition theorem of Birkhoff–von Neumann theorem is given for the case where entries can be positive or negative. The special case of an integral matrix is discussed and some balancing properties which are trivial for the classical case (non-negative entries only in the matrix) are shown to be NP-complete. Some relaxations are presented for solving the balancing problem.