Smooth well-balanced orientations with prescribed in-degrees

From Egres Open
Jump to: navigation, search

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


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].


  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. 2.0 2.1 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.