Distributed recoloring

DOI10.4230/LIPICS.DISC.2018.12MaRDI QIDQ5090902zbMATH OpenOpenAlexFDO

Authors Marthe Bonamy, Paul Ouvrard, Mikaël Rabie, Jukka Suomela, Jara Uitto

Publication date 21 July 2022

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

zbMATH Keywords

graph algorithmsdistributed systemslocal computations

Mathematics Subject Classification ID

Graph algorithms (graph-theoretic aspects) (05C85) Graph theory (including graph drawing) in computer science (68R10) Modes of computation (nondeterministic, parallel, interactive, probabilistic, etc.) (68Q10) Coloring of graphs and hypergraphs (05C15) Distributed algorithms (68W15) Network design and communication in computer systems (68M10)

Abstract: Given two colorings of a graph, we consider the following problem: can we recolor the graph from one coloring to the other through a series of elementary changes, such that the graph is properly colored after each step? We introduce the notion of distributed recoloring: The input graph represents a network of computers that needs to be recolored. Initially, each node is aware of its own input color and target color. The nodes can exchange messages with each other, and eventually each node has to stop and output its own recoloring schedule, indicating when and how the node changes its color. The recoloring schedules have to be globally consistent so that the graph remains properly colored at each point, and we require that adjacent nodes do not change their colors simultaneously. We are interested in the following questions: How many communication rounds are needed (in the LOCAL model of distributed computing) to find a recoloring schedule? What is the length of the recoloring schedule? And how does the picture change if we can use extra colors to make recoloring easier? The main contributions of this work are related to distributed recoloring with one extra color in the following graph classes: trees, $3$-regular graphs, and toroidal grids.

Recommendations

• Dynamic graph coloring
• Finding paths between 3-colorings
• Dynamic graph coloring
• Fast recoloring of sparse graphs
• On the complexity of distributed graph coloring

Cites work

• A reconfigurations analogue of Brooks' theorem and its consequences
• A very simple algorithm for estimating the number of k‐colorings of a low‐degree graph
• An optimal distributed \((\Delta+1)\)-coloring algorithm?
• Brief announcement: An exponential separation between randomized and deterministic complexity in the LOCAL model
• Deterministic \(({\delta} + 1)\)-coloring in sublinear (in \({\delta}\)) time in static, dynamic and faulty networks
• Distributed Coloring in Sparse Graphs with Fewer Colors
• Distributed Graph Coloring: Fundamentals and Recent Developments
• Fast recoloring of sparse graphs
• Finding paths between 3-colorings
• Finding paths between graph colourings: PSPACE-completeness and superpolynomial distances
• Kempe classes and the Hadwiger conjecture
• Kempe equivalence of colourings of cubic graphs
• LCL problems on grids
• Mixing 3-colourings in bipartite graphs
• On a conjecture of Mohar concerning Kempe equivalence of regular graphs
• Recoloring graphs via tree decompositions
• The complexity of bounded length graph recoloring and CSP reconfiguration

Cited in

(4)

• Distributed reconfiguration of maximal independent sets
• Brief announcement: Distributed reconfiguration of spanning trees
• Characterizing circular colouring mixing for pq<4 $\frac{p}{q}\lt 4$
• Distributed Reconfiguration of Maximal Independent Sets

This page was built for publication: Distributed recoloring

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