Deterministic fast edge coloring for bipartite graphs in distributed computing
Fast Distributed $(Δ+ 1)$-Edge Coloring in Bipartite Graphs
Distributed, Parallel, and Cluster ComputingData Structures and Algorithms
Summary
Edge coloring means coloring the connections between points in a network so that no two connections that meet share the same color. This paper shows how to do this quickly and deterministically on special types of networks called bipartite graphs, where the points can be split into two groups with no connections within the same group. The method works efficiently even when computers don’t know which group they belong to. This improves on previous approaches that needed more time or randomness to find such colorings.
What this means in practice
- •For network schedulers: Reduce scheduling conflicts by efficiently coloring network links in bipartite topologies, enabling faster, conflict-free communication coordination.
- •For parallel computing engineers: Optimize resource allocation in bipartite task-processor assignment problems by using faster deterministic edge colorings to minimize contention.
A theory result. No direct application yet.
Authors
Yann Bourreau, Sebastian Brandt, Ananth Narayanan
Abstract
We show that, on bipartite $n$-vertex graphs in the LOCAL model of distributed computation, $(Δ+ 1)$-edge coloring can be solved deterministically in $O(f(Δ) \log n)$ rounds for some function $f$. In particular this implies a deterministic $O(\log n)$-round upper bound for $(Δ+ 1)$-edge coloring on bipartite constant-degree graphs. Our results improve on the previous state-of-the-art bounds (which hold already on general graphs) whose $n$-dependencies are $\widetilde{O}(\log^5 n)$ rounds deterministically and $\widetilde{O}(\log^2 n)$ rounds randomized [Bernshteyn and Dhawan, J.\ Comb.\ Theory 2025]. In fact, we obtain the aforementioned results already for a more restrictive version of $(Δ+ 1)$-edge coloring that corresponds to a \emph{local-palette} strengthening of Vizing's theorem shown recently to hold [Christiansen, STOC 2023]. In this version, every edge $\{u, v\}$ has to be colored with a color from $\{1, \dots, \max(\operatorname{deg}(u), \operatorname{deg}(v))+ 1\}$. For all of our results, the vertices do not need to know on which side of the bipartition they lie---the structural promise of bipartiteness suffices.