Difference between revisions of "Open Problems:102"
(Created page with "{{Header |title=Making edges happy in the LOCAL model |source=wola19 |who=Jukka Suomela }} In this question, the input is the underlying graph $G=(V,E)$, promised to have max...") |
m |
||
| Line 4: | Line 4: | ||
|who=Jukka Suomela | |who=Jukka Suomela | ||
}} | }} | ||
| − | + | 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. | |
| − | 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 | ||
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. | 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$? | '''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$? | ||
Revision as of 02:43, 25 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$?
