Smooth well-balanced orientations with prescribed in-degrees

Let $$G=(V,E)$$ be an undirected graph, and $$T \subseteq V$$ a set of nodes of odd degree. When does an orientation $$D$$ of $$G$$ exist which is

i) smooth (the in-degree and out-degree of every node differ by at most one),

ii) well-balanced (that is $$\lambda_D(u,v) \geq \left\lfloor \frac{\lambda_G(u,v)}{2}\right\rfloor$$ for every $$u,v \in V$$ , where $$\lambda$$ is the local edge-connectivity), and

iii) the in-degree is less than the out-degree at the nodes in $$T$$ ?

Florian Hörsch and Zoltán Szigeti proved that deciding whether such an orientation exists is NP-complete.

Remarks

Nash-Williams' strong orientation theorem corresponds to the case $$T=\emptyset$$ . One approach would be to find a description of the polyhedron of in-degrees of smooth well-balanced orientations. However there is not much hope for such a description: it was shown in that the natural cut inequalities do not describe this polyhedron and it was shown in that optimization over this polyhedron is NP-hard. In many related problems were shown to be NP-complete, for example if $$G=(V,E)$$ is an undirected graph, and $$T_1,T_2 \subseteq V$$ are disjoint sets of odd-degree nodes then it is NP-hard to decide whether a smooth well-balanced orientation D of G exists with $$\varrho_D(v)\gt\delta_D(v)$$ for every $$v\in T_1$$ and $$\varrho_D(v)\lt\delta_D(v)$$ for every $$v\in T_2$$ . See also and .