CS Paper Radar

More Efficient Parallel $(Δ+1)$-Edge Coloring

Jeremy T. Fineman, Seyed Ali Mohammadi

cs.DS ·submitted 2026-09-28 17:38 UTC · v1

Abstract

This paper gives two parallel algorithms for $Δ+1$ edge coloring, where $Δ$ denotes the maximum degree of any vertex. The first is a deterministic parallel algorithm with $\tilde{O}(Δ^3)$ span and $\tilde{O}(m Δ^3)$ work. Our second algorithm and our main result is a more efficient randomized algorithm, achieving $\tilde{O}(Δ^2)$ span and $\tilde{O}(m Δ^2 )$ work both with high probability. These bounds substantially improve over the recent deterministic parallel algorithm of Elkin and Khuzman, which has $\tilde{O}(Δ^4)$ span and $\tilde{O}(m Δ^5)$ work. Our deterministic algorithm thus represents a $\tilde{O}(Δ)$ improvement on span and $\tilde{O}(Δ^2)$ on work compared to their algorithm, and our randomized algorithm improves the span and work by $\tilde{O}(Δ^2)$ and $\tilde{O}(Δ^3)$ factors, respectively. Moreover, our improvements do not come at the expense of larger logarithmic factors.

Closest papers

Nearest neighbours by meaning across the whole index.

A Fast Deterministic Algorithm for $(Δ+1)$-edge coloring in CONGEST

cs.DC ·2026-08-19 ·Sebastian Brandt, Ananth Narayanan, Alexandre Nolin
theory similarity 0.74
Abstract

Vizing's theorem states that any graph of maximum degree $Δ$ can be properly edge-colored with $Δ+ 1$ colors (which is optimal in general). A recent breakthrough result by Bernshteyn showed that such a $(Δ+ 1)$-edge coloring can be found deterministically in $poly(Δ,\log n)$ rounds in the LOCAL model of distributed computing, where $n$ denotes the number of vertices of the input graph [J. Comb. Theory 2022]. Since then, the exponent in the $poly(\log n)$-part of the runtime has been improved by Christiansen [STOC 2023] and Bernshteyn and Dhawan [J. Comb. Theory, Series B, 2025]. However, the algorithms used in all of these works use large messages, leaving open the question for efficient algorithms in the more restrictive CONGEST model. We answer this question by presenting the first $poly(Δ,\log n)$-round algorithm for $(Δ+ 1)$-edge coloring in the CONGEST model. Our algorithm is deterministic and the $n$-dependency of its runtime, $\tilde{O}(\log^5 n)$, matches the best published dependency in the LOCAL model.

0.16

Sharper Gaussian Covers in the Bansal--Huang--Lee Coloring Framework

cs.DS ·2026-09-30 ·Konstantin Makarychev, Yury Makarychev
theory similarity 0.71
Abstract

Bansal, Huang, and Lee recently gave a polynomial-time algorithm that colors every $3$-colorable graph on $n$ vertices with $O(n^{0.19539})$ colors. We improve their bound to $O(n^{0.17794})$ colors. The improvement comes from a sharper rule for combining Gaussian covers. We prove the rule from Ehrhard's inequality by comparing the probability that a Gaussian vector misses a polyhedron at two thresholds. At the farther threshold a union bound records how many halfspaces define the polyhedron, and this information reduces the loss in the combination. We then organize the successive neighborhood steps of the Bansal-Huang-Lee argument into a single recursion. The smaller loss lets the recursion run one step farther than before, and at that step it would require more distinct vertices than the graph contains. This rules out the remaining case. Combining the resulting bounded-degree guarantee with the dense-graph algorithm of Kawarabayashi, Thorup, and Yoneda gives a randomized polynomial-time algorithm that colors every $3$-colorable graph on $n$ vertices with $O(n^{0.17794})$ colors.

0.04

Faster Minimum k-Cut II: Improved Randomized and Deterministic Algorithms for Weighted Graphs

cs.DS ·2026-08-17 ·Trevor Vaughn
similarity 0.71
Abstract

The Minimum $k$-Cut problem asks for a minimum-weight set of edges whose removal leaves an undirected weighted graph with at least $k$ connected components. We consider only $k\ge3$. The fastest previous algorithm for weighted graphs ran in $n^{k-2}(m+n)(\log n)^{O(k^2)}$ randomized time~\cite{LV26}; on dense graphs this is $\widetilde O_k(n^k)$, and for $k=3$ it gives an $\widetilde O(nm)$-time algorithm. We improve the dense-graph exponent from $k$ to $k-1$ and obtain the same exponent deterministically. After aggregating parallel edges in $O(m)$ time, our randomized algorithm runs with high probability in \begin{equation*} k^{O(k^2)}n^{k-1}\log^2n \end{equation*} time, while our deterministic algorithm runs in \begin{equation*} k^{O(k^2)}n^{k-1}\log^{O(1)}n \end{equation*} time. In particular, weighted Minimum $3$-Cut can be solved in $O(n^2\log^2 n)$ randomized time and in $\widetilde O(n^2)$ deterministic time. The algorithms have two main components. First, we give a faster algorithm for weighted Minimum $3$-Cut. After handling optima with a very small side and optima with two light sides, the remaining optimum has a unique structured side. Tree packing reduces its completion to a batched collection of $2$-respecting cut problems. Second, we reduce Minimum $k$-Cut to Minimum $3$-Cut by enumerating a bounded family of light-cut candidates and recursively completing either side of each candidate. If the enumeration produces too many cuts, then we can instead produce an optimum $k$-cut directly. We derandomize the $3$-cut algorithm using a deterministic near-minimum-cut skeleton, and derandomize the reduction using a specialized $4$-cut algorithm using the skeleton, the constructive light-cut bounds, and the deterministic spectral sparsifier of \cite{BSS12}.

0.23

Fast Distributed $(Δ+ 1)$-Edge Coloring in Bipartite Graphs

cs.DC cs.DS ·2026-10-15 ·Yann Bourreau, Sebastian Brandt, Ananth Narayanan
theoryhot direction similarity 0.71
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.

0.21

Faster Exact Algorithms for 3- and 4-Coloring: Deterministic Improvements and Further Randomized Speedups

cs.DS ·2026-11-02 ·Ryosuke Yamano, Tetsuo Shibuya
similarity 0.70
Abstract

We study exact exponential-time algorithms for 3- and 4-coloring. For 3-coloring, the best previously published running-time bound is $O^*(1.3289^n)$, due to Eppstein (SODA 2001). We improve this bound to $O^*(1.3204^n)$ deterministically and $O^*(1.3159^n)$ using randomization. For 4-coloring, the best previously known running-time bound is $O^*(1.7159^n)$, due to Wu, Gu, Jiang, Shao, and Xu (ESA 2024). We improve this bound to $O^*(1.6975^n)$ deterministically and $O^*(1.6933^n)$ using randomization. Our algorithms for both problems combine constraint satisfaction algorithms with dynamic programming over tree and path decompositions, exploiting their complementary strengths on different graph structures. For 6-coloring, the best published randomized running-time bound is exponentially smaller than the best published deterministic bound. For 3- and 4-coloring, however, no such improvement through randomization was previously known. To the best of our knowledge, our results provide the first randomized running-time bounds for these two problems that exponentially improve upon the best previously published deterministic bounds. This raises the question of whether randomization offers an inherent exponential advantage for 3- and 4-coloring.

0.41

True Work-Efficiency in Parallel Derandomization

cs.DS ·2026-08-22 ·Mohsen Ghaffari, Cheng Jiang
similarity 0.68
Abstract

A longstanding limitation of known techniques for parallel derandomization was that they incurred at least polylogarithmic overhead in work. For instance, for fundamental and frequently used problems such as maximal independent set, maximal matching, and $(Δ+1)$-coloring, where $Δ$ denotes the maximum degree of the graph, the best-known deterministic parallel algorithms with polylogarithmic depth used $Ω((m+n)\mathrm{poly}(\log n))$ work on $n$-vertex, $m$-edge graphs; see, e.g., Luby [FOCS '88]. Consequently, at least $\mathrm{poly}(\log n)$ processors were needed for these algorithms to outperform straightforward single-processor algorithms. Recently, Ghaffari and Grunau [FOCS '25] introduced a new parallel derandomization method that substantially reduced the overhead from $\mathrm{poly}(\log n)$ to $\mathrm{poly}(\log\log n)$, achieving work bounds of $O((m+n)\mathrm{poly}(\log\log n))$. In this paper, we settle this line of research by obtaining linear work bounds of $O(m+n)$, thereby achieving truly work-efficient parallel derandomization.

0.37

Constant-Time Dynamic Edge Coloring via Dynamic Splitting and LLL

cs.DS ·2026-11-04 ·Mohsen Ghaffari, Sijin Peng
similarity 0.68
Abstract

We give a dynamic algorithm that maintains a near-optimal edge coloring in constant expected time per update. For every fixed $ε>0$, the algorithm maintains a $(1+ε)Δ$ edge coloring under edge insertions and deletions in $\mathrm{poly}(1/ε)$ worst-case expected update time against an oblivious adversary, provided $Δ\geΔ_ε=\widetildeΘ(1/ε^2)$. The previous constant-time algorithm of Bhattacharya, Costa, Panski, and Solomon (BCPS) required $Δ\ge(\log n/ε^4)^{Θ(\log(1/ε)/ε)}$, where $n$ is the number of vertices. We remove this dependence on $n$, answering their open question. Our approach differs substantially from that of BCPS, which relied on coloring in locally tree-like subgraphs. Instead, we draw on distributed algorithms that organize partial coloring through successive applications of the Lovász Local Lemma (LLL). We develop a dynamic LLL solver with worst-case expected update bounds and a dynamic splitting algorithm that partitions edges into low-degree subgraphs. A key technical contribution is a bottom-up method for iterative splitting, which avoids the logarithmic overhead of maintaining successive levels. It achieves constant expected update time by adaptively choosing which levels to inspect and repair, rather than inspecting every level after each update. We believe these dynamic splitting and LLL tools can be of interest beyond edge coloring.

0.20

An $O(n^{0.1537})$-Coloring Algorithm for 3-Colorable Graphs

cs.DS ·2026-10-26 ·Kaisei Deguchi, Ken-ichi Kawarabayashi, Hirotaka Yoneda, Masataka Yoneda
similarity 0.67
Abstract

We present a polynomial-time randomized algorithm that colors every $n$-vertex $3$-colorable graph with $O(n^{0.1537})$ colors. This improves upon the previous bound of $O(n^{0.1954})$ colors by Bansal, Huang, and Lee (SODA '27). To achieve this result, we introduce a new algorithmic framework for finding a large independent set from a solution to the vector coloring SDP. Combined with the (combinatorial) dense-progress algorithm of Kawarabayashi, Thorup, and Yoneda (STOC '24), this framework yields an $n^{1/6 + o(1)}$-coloring algorithm. Furthermore, we strengthen the SDP-based algorithm specifically for 3-colorable graphs to achieve $O(n^{0.1537})$ colors.

0.19