# Smooth well-balanced orientations with prescribed in-degrees

Jump to: navigation, search

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$?

## 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 [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 $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 [3] and [4].

## References

1. 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. A. Bernáth, Hardness results for well-balanced orientations EGRES Technical Report no. 2006-05.
3. Z. Király, Z. Szigeti, Notes on well-balanced orientations EGRES Technical Report no. 2004-10.
4. 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.