# Smooth well-balanced orientations with prescribed in-degrees

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

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

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

* iii)* the in-degree is less than the out-degree at the nodes in [math]T[/math]?

## Remarks

Nash-Williams' strong orientation theorem corresponds to the case [math]T=\emptyset[/math]. 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 ^{[1]} that the natural cut inequalities do not describe this polyhedron and it was shown in ^{[2]} that optimization over this polyhedron is NP-hard. In ^{[2]} many related problems were shown to be NP-complete, for example if [math]G=(V,E)[/math] is an undirected graph, and [math]T_1,T_2 \subseteq V[/math] 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 [math]\varrho_D(v)\gt\delta_D(v)[/math] for every [math]v\in T_1[/math] and [math]\varrho_D(v)\lt\delta_D(v)[/math] for every [math]v\in T_2[/math]. See also ^{[3]} and ^{[4]}.

## References

- ↑ S. Iwata, T. Király, Z. Király, Z. Szigeti,
*On well-balanced orientations,counter-examples for related problems*EGRES Technical Report no. 2004-16. - ↑
^{2.0}^{2.1}A. Bernáth,*Hardness results for well-balanced orientations*EGRES Technical Report no. 2006-05. - ↑ Z. Király, Z. Szigeti,
*Notes on well-balanced orientations*EGRES Technical Report no. 2004-10. - ↑ A. Bernáth and G. Joret,
*Well-balanced orientations of mixed graphs*Inf. Process. Lett., 106(4):149-151, 2008. DOI link, EGRES Quick Proof No. 2007-01.