Hardness results for well-balanced orientations
Attila Bernáth · 2006
In 1960 Nash-Williams proved his strong orientation theorem about the existence of well-balanced orientations. In this paper we show that it is NP hard to find a minimum cost well-balanced orientation (given the cost for the two possible orientations of each edge) or a well-balanced orientation satisfying lower and upper bounds on the out-degrees at each node. Similar results are proved for best-balanced orientations and other related problems are considered, too.