Brief Announcement: Sinkless Orientation Is Hard Also in the Supported LOCAL Model

Janne Korhonen (1) , Ami Paz (2, 3, 4) , Joel Rybicki (5) , Stefan Schmid (6) , Jukka Suomela (7)

1 Department of Physics
2 ParSys - Systèmes Parallèles - LISN
3 LISN - Laboratoire Interdisciplinaire des Sciences du Numérique
4 CNRS - Centre National de la Recherche Scientifique
5 IST Austria - Institute of Science and Technology [Klosterneuburg, Austria]
6 University of Vienna [Vienna]
7 Aalto University

We show that any algorithm that solves the sinkless orientation problem in the supported LOCAL model requires Ω(log n) rounds, and this is tight. The supported LOCAL is at least as strong as the usual LOCAL model, and as a corollary this also gives a new, short and elementary proof that shows that the round complexity of the sinkless orientation problem in the deterministic LOCAL model is Ω(log n).

Mots clés: Supported LOCAL model; sinkless orientation; round elimination; Theory of computation → Distributed computing models

Domaines: Informatique [cs]; Calcul parallèle, distribué et partagé [cs.DC]

Janne Korhonen, Ami Paz, Joel Rybicki, Stefan Schmid, Jukka Suomela. Brief Announcement: Sinkless Orientation Is Hard Also in the Supported LOCAL Model. DISC'21, Oct 2021, Freiburg, Germany. ⟨10.4230/LIPIcs.DISC.2021.58⟩. ⟨hal-04288790⟩