On the complexity of finding well-balanced orientations with upper bounds on the out-degrees

Abstract

We show that the problem of deciding whether a given graph $G$ has a well-balanced orientation $\vec{G}$ such that $d_{\vec{G}}^{+}(v)\le \ell (v)$ for all $v\in V(G)$ for a given function $\ell :V(G)\to {\mathbb{Z}}_{\ge 0}$ is NP-complete. We also prove a similar result for best-balanced orientations. This improves a result of Bern\' ath, Iwata, Kir\' aly, Király and Szigeti and answers a question of Frank.