Problem 102: Making Edges Happy in the LOCAL Model

Suggested by	Jukka Suomela
Source	WOLA 2019
Short link	https://sublinear.info/102

In this question, the input is the underlying graph $G=(V,E)$, promised to have maximum degree at most $\Delta$, and the goal is to compute an orientation of the edges of $E$ which makes all edges “happy.” Specifically, for any given orientation of the edges, the load of a node $v\in V$ is its number of incoming edges. An edge $e$ is then said to be happy if switching its orientation does not make it point to a smaller-node load.

One can show by a greedy argument that there always exists an orientation making all edges happy. Moreover, a surprising result established that, in the LOCAL model, such a configuration could be found in $\operatorname{poly}(\Delta)$ rounds, independent of the number of nodes $n$. However, the question of the dependence on $\Delta$ remains wide open, as even a $\operatorname{poly}\!\log(\Delta)$ upper bound is not ruled out.

Question: What is the right dependence on $\Delta$? Can one show any lower polynomial lower bound, e.g., $\Delta^{0.1}$, $\sqrt{\Delta}$, or $\Delta$?