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