On the Complexity of Distributed Splitting Problems

Research output: Chapter in Book/Report/Conference proceedingConference contributionScientificpeer-review

Researchers

  • Philipp Bamberger
  • Mohsen Ghaffari
  • Fabian Kuhn
  • Yannic Maus
  • Jara Uitto

Research units

  • University of Freiburg
  • Technion
  • Swiss Federal Institute of Technology Zurich
  • Eidgenössische Technische Hochschule Zürich - ETH Zürich

Abstract

One of the fundamental open problems in the area of distributed graph algorithms is whether randomization is needed for efficient symmetry breaking. While there are poly log n-time randomized algorithms for all the classic symmetry breaking problems, for many of them, the best deterministic algorithms are almost exponentially slower. The following basic local splitting problem, which is known as weak splitting, takes a central role in this context: Each node of a graph G=(V,E) has to be colored red or blue such that each node of sufficiently large degree has at least one neighbor of each color. Ghaffari, Kuhn, and Maus [STOC '17] showed that this seemingly simple problem is complete w.r.t. the above fundamental open question in the following sense: If there is an efficient poly log n-time determinstic distributed algorithm for weak splitting, then there is such an algorithm for all locally checkable graph problems for which an efficient randomized algorithm exists. We investigate the distributed complexity of weak splitting and some closely related problems and we in particular obtain the following results: We obtain efficient algorithms for special cases of weak splitting in nearly regular graphs. We show that if δ=Ø(log n) and Δ are the minimum and maximum degrees of G, weak splitting can be solved deterministically in time O #916;(√ over δ • poly(log n)). Further, if δ = Ø(log log n) and Δ ≤ 2ε δ, the time complexity is O(Δ over δ⋅poly(log log n)). We prove that the following two related problems are also complete in the same sense: (I) Color the nodes of a graph with C ≤ poly log n colors such that each node with a sufficiently large polylogarithmic degree has at least 2 log n different colors among its neighbors, and (II) Color the nodes with a large constant number of colors so that for each node of a sufficiently large at least logarithmic degree d(v), the number of neighbors of each color is at most (1-εd(v) for some constant ε > 0.

Details

Original languageEnglish
Title of host publicationPODC '19 -Proceedings of the 2019 ACM Symposium on Principles of Distributed Computing
Publication statusPublished - 2019
MoE publication typeA4 Article in a conference publication
EventACM Symposium on Principles of Distributed Computing - Toronto, Canada
Duration: 29 Jul 20192 Aug 2019
Conference number: 38

Conference

ConferenceACM Symposium on Principles of Distributed Computing
Abbreviated titlePODC
CountryCanada
CityToronto
Period29/07/201902/08/2019

ID: 38157591