Path colorings in bipartite graphs

The theorem of König on edge colorings in bipartite multigraphs can be seen as the integral version of the theorem of Birkhoff and von Neumann on bistochastic matrices. Here we consider the more general case where the matrix A=(aij) to be decomposed has real entries (instead of non negative entries). We shall concentrate on the integral case. Interpretation in terms of arc and path colorings are given with some properties of these decompositions and one shows that some balancing problems which are trivial in the classical case are now NP-complete. We also introduce requirements on the parity of the paths in the decompositions.