On the complexity of circulations
Esther M. Arkin, Christos H. Papadimitriou · Journal of Algorithms · 1986
We present a polynomial-time algorithm for producing a feasible real-valued circulation in undirected graphs with upper and lower bounds, based on Seymour's characterization. For directed graphs, an efficient algorithm follows from a classical result by Hoffman. We show that, for mixed graphs, i.e., graphs having both directed and undirected edges, the problem is NP-complete.