Brief announcement: Sinkless orientation is hard also in the supported LOCAL model

Korhonen, Janne H.; Paz, Ami; Rybicki, Joel; Schmid, Stefan; Suomela, Jukka

doi:10.4230/LIPIcs.DISC.2021.58

Janne H. Korhonen · Ami Paz · Joel Rybicki · Stefan Schmid · Jukka Suomela

Brief announcement: Sinkless orientation is hard also in the supported LOCAL model

DISC 2021 · 35th International Symposium on Distributed Computing, online, October 2021 · doi:10.4230/LIPIcs.DISC.2021.58

authors’ version publisher’s version arXiv.org

Abstract

We show that any algorithm that solves the sinkless orientation problem in the supported LOCAL model requires $\Omega(\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 $\Omega(\log n)$.

Publication

Seth Gilbert (Ed.): 35th International Symposium on Distributed Computing (DISC 2021), volume 209 of Leibniz International Proceedings in Informatics (LIPIcs), pages 58:1–58:4, Schloss Dagstuhl–Leibniz-Zentrum für Informatik, 2021

ISBN 978-3-95977-210-5

Longer Version

Alkida Balliu, Janne H. Korhonen, Fabian Kuhn, Henrik Lievonen, Dennis Olivetti, Shreyas Pai, Ami Paz, Joel Rybicki, Stefan Schmid, Jan Studený, Jukka Suomela, and Jara Uitto: Sinkless orientation made simple · SOSA 2023

This material is presented to ensure timely dissemination of scholarly and technical work. Copyright and all rights therein are retained by authors or by other copyright holders. All persons copying this information are expected to adhere to the terms and constraints invoked by each author’s copyright. In most cases, these works may not be reposted without the explicit permission of the copyright holder.