Minimum Cost Nowhere-zero Flows and Cut-balanced Orientations

Karthekeyan Chandrasekaran, Siyue Liu, R. Ravi

Flows and colorings are disparate concepts in graph algorithms -- the former is tractable while the latter is intractable. Tutte introduced the concept of nowhere-zero flows to uni…