Open Problems:102 - Revision history

Krzysztof Onak: Krzysztof Onak moved page Waiting:Making edges happy in the LOCAL model to Open Problems:102 without leaving a redirect

2019-08-26T18:36:54Z

Krzysztof Onak moved page Waiting:Making edges happy in the LOCAL model to Open Problems:102 without leaving a redirect

Krzysztof Onak: Updating the header

2019-08-26T18:36:39Z

Updating the header

Krzysztof Onak at 02:43, 25 August 2019

2019-08-25T02:43:27Z

Ccanonne: 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..."

2019-08-07T21:47:33Z

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..."

New page

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

← Older revision	Revision as of 18:36, 26 August 2019
(No difference)

@@ Line 1: / Line 1: @@
 {{Header
 |source=wola19
 |who=Jukka Suomela

@@ Line 4: / Line 4: @@
 |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 &ldquo;happy.&rdquo; 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$?