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]?
Florian Hörsch and Zoltán Szigeti [1] proved that deciding whether such an orientation exists is NP-complete.
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 [2] that the natural cut inequalities do not describe this polyhedron and it was shown in [3] that optimization over this polyhedron is NP-hard. In [3] 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 [4] and [5].
References
- ↑ Florian Hörsch, Zoltán Szigeti, On the complexity of finding well-balanced orientations with upper bounds on the out-degrees, arXiv:2202.13759 (2022), DOI link
- ↑ 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.
- ↑ 3.0 3.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.
