A fast distributed algorithm for (+1)-edge-coloring

DOI10.1016/J.JCTB.2021.10.004MaRDI QIDQ2664558zbMATH OpenOpenAlexFDO

Authors Anton Bernshteyn

Publication date 17 November 2021

Published in Journal of Combinatorial Theory. Series B (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/2006.15703

zbMATH Keywords

distributed algorithmsedge-coloringhappy edgeshopeful chainsLOCAL modelmulti-step Vizing's algorithmsuccessful chains

Mathematics Subject Classification ID

Coloring of graphs and hypergraphs (05C15) Graph algorithms (graph-theoretic aspects) (05C85) Distributed algorithms (68W15)

Abstract: We present a deterministic distributed algorithm in the LOCAL model that finds a proper $(Delta+1)$-edge-coloring of an $n$-vertex graph of maximum degree $Delta$ in $mathrmpoly(Delta,logn)$ rounds. This is the first nontrivial distributed edge-coloring algorithm that uses only $Delta+1$ colors (matching the bound given by Vizing's theorem). Our approach is inspired by the recent proof of the measurable version of Vizing's theorem due to Greb'ik and Pikhurko.

Review text

A local algorithm is a distributed algorithm that runs in constant time, which is independent of the size of the network concerned. In this paper, the author proposes a local algorithm to find a proper \((\Delta+1)\)-edge-coloring of a graph of order \(n\) and maximum degree \(\Delta\). In the beginning, he establishes the existence of such an algorithm that computes a \((\Delta+1)\)-edge-coloring of a graph in \(\mathrm{poly}(\Delta, \log n)\) rounds. In order to establish the same, the author uses the distributed approximation algorithm for hypergraph maximum matching and related arguments. Following this, he also explains that there is a connected augmenting subgraph \(H\) of the graph \(G\) under consideration such that \(|E(H)| \le O((\log n)^2)\). In the following section, the notion of happy edges and the process of shifting have been introduced and explained with the help of suitable illustrations. The concepts of hopeful chains and successful chains follow and based on these, some interesting results are proved to establish the relations between these concepts. Later, the author describes a randomized algorithm, namely Multi-Step Vizing Algorithm, to build a happy chain starting with a specified uncolored edge of the graph and perform a probabilistic analysis of this algorithm. The paper is well-written in insightful and logical manner. The style of presentation makes the reading a delightful experience. The author deserves much appreciation for the preparation of such a wonderful paper.

Recommendations

• Towards the locality of Vizing's theorem
• Deterministic distributed edge-coloring with fewer colors
• scientific article; zbMATH DE number 1875427
• Fast distributed graph coloring with O() colors
• (2-1)-edge-coloring is much easier than maximal matching in the distributed setting

Cites work

• A fast and simple randomized parallel algorithm for the maximal independent set problem
• A Simple Parallel Algorithm for the Maximal Independent Set Problem
• Deterministic distributed edge-coloring with fewer colors
• Distributed Graph Coloring: Fundamentals and Recent Developments
• Graph edge coloring. Vizing's theorem and Goldberg's conjecture
• Graph theory
• scientific article; zbMATH DE number 6850477 (Why is no real title available?)
• Locality in Distributed Graph Algorithms
• Measurable versions of Vizing's theorem
• Parallel Symmetry-Breaking in Sparse Graphs
• Polylogarithmic-time deterministic network decomposition and distributed derandomization
• Towards the locality of Vizing's theorem

Cited in

(26)

• Near-optimal, distributed edge colouring via the nibble method
• Linial for lists
• Improved distributed degree splitting and edge coloring
• Randomised distributed MIS and colouring algorithms for rings with oriented edges in \(O(\sqrt{\log n})\) bit rounds
• A fast parallel algorithm to color a graph with Δ colors
• scientific article; zbMATH DE number 6850477 (Why is no real title available?)
• scientific article; zbMATH DE number 1875427 (Why is no real title available?)
• Faster Deterministic Distributed Coloring Through Recursive List Coloring
• Towards the locality of Vizing's theorem
• Deterministic distributed edge-coloring with fewer colors
• Brooks’ theorem in graph streams: a single-pass semi-streaming algorithm for ∆-coloring
• The power of multi-step Vizing chains
• Borel Vizing's theorem for graphs of subexponential growth
• Caching connections in matchings
• Sparsity-parameterised dynamic edge colouring
• Fast algorithms for Vizing's theorem on bounded degree graphs
• Fast and simple (1 + ) -edge-coloring of dense graphs
• Measurable Vizing's theorem
• Edge-coloring sparse graphs with Colors in quasilinear time
• A linear-time algorithm for (1+)-edge-coloring
• Faster edge coloring by partition sieving
• Distributed edge coloring in time polylogarithmic in \({\Delta }\)
• Vizing's theorem in near-linear time
• Improved streaming edge coloring
• Edge coloring of multigraphs with very high multiplicities
• A self-stabilizing \((\Delta +4)\)-edge-coloring algorithm for planar graphs in anonymous uniform systems

This page was built for publication: A fast distributed algorithm for \((\Delta+1)\)-edge-coloring

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2664558)