CS Paper Radar

One Color Preprocessing Improves DSATUR

Adam Nouira, Lucas Isenmann

cs.AI ·submitted 2026-09-15 10:35 UTC · v1
benchmark

Abstract

The Graph Coloring Problem (GCP) is NP-hard and DSATUR stands as one of the fastest heuristics for it despite producing colorings that typically use more colors than state-of-the-art coloring algorithms. We propose SSLD (Semidefinite Spectral Learning with DSATUR), which improves DSATUR by preprocessing a first good color class before letting DSATUR complete coloring the rest of the given graph. We obtain this color class from a Semidefinite Programming (SDP), similar to an SDP used to compute the Lovász theta number. To the best of our knowledge, SSLD is the first approach to improve DSATUR by preprocessing through fixed color classes. We evaluate SSLD against DSATUR and against a naive 1-color-class preprocessing algorithm on DIMACS instances, random graphs (Erdős--Rényi, Watts-Strogatz, Barabási--Albert), Frequency Assignment and Job Shop Scheduling instances. SSLD matches or beats DSATUR in almost every case across over 1600 benchmark instances, and out performs the naive GISD baseline, allows us to confirm the value brought by the SDP-guided choice of the first color class. This quality comes at a runtime cost of roughly 195 times slower that DSATUR, but demonstrating that SDP-guided preprocessing of a first color class is a direction for future improvements.

Closest papers

Nearest neighbours by meaning across the whole index.

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.66
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

Scone: Symmetry-aware Neural Combinatorial Optimization for Graph Coloring

cs.LG ·2026-11-18 ·Paolo Pellizzoni, Melanie Weber
similarity 0.62
Abstract

Graph coloring, which entails assigning colors to nodes such that no adjacent nodes have the same color, is a fundamental combinatorial optimization problem. In general, however, finding a node coloring with no monochromatic edges given a fixed palette is NP-hard. This motivates learning-based methods that can learn to exploit recurring structure across instances to efficiently produce high-quality colorings. Crucially, the validity of a coloring is invariant to permutations of the colors, and we show that exploiting this symmetry reduces the size of the effective state space over which the model has to learn its policy. At the same time, the coloring algorithm must be able to break some symmetries, for example to assign different colors to two adjacent nodes belonging to the same automorphism orbit. In this paper, we introduce Scone, a model that uses a color-equivariant graph neural network to construct colorings sequentially, allowing information from previous assignments to propagate and break node symmetries. Scone achieves perfect solution quality with low inference times across several graph coloring tasks, including on sudoku_extreme and register allocations, and showcases generalization to graph families not encountered during training.

0.19

On the Parameterized Complexity of Coloring Discovery

cs.CC cs.DMcs.DS ·2026-09-09 ·Eric Decker, Sebastian Siebertz
similarity 0.60
Abstract · 22 pages, 4 figures, submitted to SOFSEM 2027

Coloring Discovery asks whether a possibly improper initial coloring can be made proper within a prescribed number of allowed changes. We study the parameterized complexity of three modification step models that were studied previously in the literature: recoloring one vertex (color flipping), swapping the colors of arbitrary vertices (color swapping), and swapping colors only across an edge (color sliding). For color flipping, we give exact fixed-parameter algorithms for the parameters vertex cover and distance to complete. For color swapping, we obtain fixed-parameter tractability for the parameter vertex cover plus the number of colors. Our lower bounds show W[1]-hardness for treedepth plus feedback vertex set in the color flipping model and for the number of colors plus bandwidth or distance to disjoint paths in the swapping and sliding models. All three variants remain NP-complete with four colors on graphs of diameter two.

0.13

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.60
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

Triangle-Free Coloring in LOCAL via Resilient Lovász Local Lemma

cs.DC cs.DS ·2026-08-13 ·Peter Davies-Peck, Xusheng Zhang
publishedbenchmarktheory similarity 0.58
Abstract · To appear at DISC 2026

The Lovász Local Lemma (LLL) is a probabilistic tool that has been shown to be of central importance in the study of distributed algorithms. For example, the constructive LLL is known to be complete for the class of locally-checkable labeling problems with $o(\log n)$ randomized complexities in the LOCAL model. One classic application of the LLL is in coloring graphs with some sparse structure, such as triangle-free graphs. Triangle-free coloring therefore serves as a benchmark problem for techniques for sublogarithmic randomized distributed algorithms. The state-of-the-art distributed triangle-free coloring algorithm of Pettie and Su [ICALP 2013, Information and Computation 2015] uses $\fracΔ{k}$ colors (where $k$ can be up to $(\frac14 - \varepsilon)\ln Δ$) and consists of $O(k+\log^* n)$ applications of the distributed LLL. However, the distributed LLL is itself a difficult problem; despite significant study, the fastest algorithms known require $O(\log_Δn)$ or $O(\fracΔ{\logΔ})+\log^{O(1)}\log n$ rounds. In this work, we adapt the Pettie-Su's algorithm so that the resulting LLL instances can be solved in $\log^{O(1)}\log n$ rounds, by employing the 'resilience' definition of Davies [SODA 2023]. This gives an $O(k)+ \log^{O(1)}\log n$ complexity (since the LLL is not needed when $k= \log^{ω(1)}\log n$), essentially causing the LLL steps to no longer be the bottleneck of the algorithm. As a corollary we obtain the first $\log^{O(1)}\log n$-round algorithms for coloring triangle-free graphs with $o(Δ)$ colors. The same framework also yields a companion girth-$5$ algorithm, using $(1+\varepsilon)Δ/\ln Δ$ colors in $O(k)+ \log^{O(1)}\log n$ rounds, matching the best known existential upper bound for the number of colors.

0.59

FirstFit online coloring in the random order model

cs.DS cs.DMmath.CO ·2026-08-30 ·Xinyu Ye, Yuechuan Xu, Zixuan Wang, Jiaying Zheng, Yaqiao Li
similarity 0.57
Abstract · 9 pages, 1 figure

The average performance of FirstFit online coloring on trees in the random order model is completely determined in recent works of Frei et al. and Bosek et al., showing $Θ(\log n /\log\log n)$ number of colors, improving the $Θ(\log n)$ colors in the adversarial model. We provide a few further results on slightly more general graph classes. Firstly, we extend their method to obtain a simple path-counting principle for sparse graph classes, which immediately yields for example that cactus graphs and uniform hypertrees exhibit a similar improvement. We then show that FirstFit uses only $O(1)$ colors on crown graphs, a standard example where adversarial arrival forces $Θ(n)$ colors. We further show that density alone (even linear minimum degree) is insufficient to guarantee $O(1)$ colors even on bipartite graphs. Finally, we identify graph classes, including unit interval graphs and some graphs of high chromatic number, for which random arrival provides only limited improvement. We end with some open problems.

0.31

Two-colour crossing minimization in complete geometric graphs is NP-hard

cs.CC cs.CG ·2026-10-22 ·Zhe Zhang, Yi Liu, Dan Yang
theorycode/data similarity 0.56
Abstract · 34 pages, 5 figures, 2 tables. Updated author information, presentation and declarations. Proof code and reproducible computations: https://…

Given a fixed straight-line drawing of a complete graph, we seek a two-colouring of its edges that minimizes monochromatic crossing pairs. We prove that the threshold decision problem is NP-complete, even for points in general position with integer coordinates. Thus exact minimization is NP-hard, resolving the complexity question posed at the Crossing Number Workshop in 2019. We reduce from MaxCut on permutation graphs by representing source vertices with classes of geometric edges, whose crossings encode source adjacencies. The target complete graph also contains every other edge between its points, and their freely chosen colours can affect the encoded cost. To control these interactions, we construct a large comparison grid with two stable colour phases and use program points to turn this reference into colour preferences on other edges. The optimum differs from a computable baseline plus the amplified minimum number of uncut source edges by an error small enough to distinguish consecutive source values. The reduction is deterministic, with polynomially many points and polynomial coordinate bit length.

0.38

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

cs.DS ·2026-09-30 ·Konstantin Makarychev, Yury Makarychev
theory similarity 0.56
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