Difference between revisions of "Open Problems:102"

From Open Problems in Sublinear Algorithms
Jump to: navigation, search
m
(Updating the header)
Line 1: Line 1:
 
{{Header
 
{{Header
|title=Making edges happy in the LOCAL model
 
 
|source=wola19
 
|source=wola19
 
|who=Jukka Suomela
 
|who=Jukka Suomela

Revision as of 18:36, 26 August 2019

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