One Color Preprocessing Improves DSATUR

1 Introduction

• GCP seeks a minimum proper coloring, but NP-hardness and exact methods’ roughly 300-vertex, 10-minute limit motivate heuristics for larger graphs.The stated runtime limit is for a random graph.Source: §1 · pp. 1–2

1.1 Approximation algorithms

• An O(n/log n)-approximation for k-coloring and SDP-based vector embeddings with randomized rounding illustrate approaches to graph-coloring approximation.The SDP approach gives O(n^0.387) colors for 3-colorable graphs and O(n^(1−3/(k+1))) for k-colorable graphs.Source: §1.1 · p. 2

1.2 Heuristics

• Greedy methods such as DSATUR and RLF are fast but use more colors than the best-known colorings, so they are now mainly used to produce initial solutions.Source: §1.2 · p. 2

1.3 The Lov´asz ϑ Function

• The Lovász ϑ function is defined through unit vectors and orthonormal representations, and is upper bounded by the chromatic number of the complement graph.Source: §1.3 · p. 3

1.4 Semidefinite Programming Formulation

• The L-SDP computes the Lovász ϑ function; its optimal Gram matrix yields an orthonormal representation, and SDP can be solved in polynomial time to arbitrary precision.Source: §1.4 · pp. 3–4

1.5 Our Contribution

• SSLD seeks to improve DSATUR by trying independent sets and returning the best coloring, using an SDP relaxation, spectral decomposition, and randomized rounding to choose sets.The paper describes the approach as the first to improve DSATUR by preprocessing with fixed color classes.Source: §1.5 · p. 4

2 DSATUR preprocessing

• The preprocessing assigns color 0 to an independent set and completes the partial coloring with DSATUR.Source: §2 · p. 4
• The final color count depends on both the independent set’s size and its vertices; even a large, poorly chosen set can leave DSATUR a harder subgraph and use more colors than plain DSATUR.Source: §2 · p. 4
• During DSATUR completion, each selected vertex receives the smallest color unused by its neighbors.Source: §2 · p. 4

3 Naive DSATUR preprocessing

• GISD fixes a maximal independent set built greedily as one color class, then completes the coloring with DSATUR.Source: §3 · p. 5
• GISD requires no SDP solve, so its overhead over plain DSATUR is negligible.Source: §3 · p. 5
• The greedy independent set receives color 0, after which DSATUR completes the coloring.Source: §3 · p. 5

4.1 The D-SDP

• GISD is the special case that replaces the spectral score with identity ordering; its arbitrary independent set can perform strictly worse than DSATUR on some instances.SSLD instead uses an ordering derived from the SDP relaxation.Source: §4.1 · p. 6
• The D-SDP encourages aligning vertices that could form a common independent set, potentially rewarding larger independent sets.Its orthogonal representation supports detecting color classes by projecting vertices onto a centroid and selecting those with high scalar products.Source: §4.1 · pp. 5–6
• The Lovász SDP is slower to compute and gives no better results than the D-SDP in Table 1.The D-SDP is related to the Lovász SDP but differs in its objective and has no proven theoretical guarantees.Source: §4.1 · pp. 5–6

4.2 Algorithm Description

• SSLD uses the D-SDP embedding to derive vertex scores, greedily extracts an independent set as color 0, and completes the remaining graph with DSATUR.Across T attempts, it returns the coloring using the fewest colors.Source: §4.2 · pp. 6–7

Parameter Selection

• T = 500 differs from T = 1000 by at most 0.2 in mean best-so-far chromatic number across tested densities and sizes.Each additional attempt adds a random projection, greedy independent-set extraction, and DSATUR completion beyond the single SDP solve.Source: Parameter Selection · p. 7

5.1 Benchmark Instances

• The evaluation includes DIMACS, Erdős–Rényi, Watts–Strogatz, Barabási–Albert, frequency-assignment, job-shop scheduling, and Spinrad–Vijayan instances.The Spinrad–Vijayan family is used as a worst-case stress test for DSATUR-based methods.Source: §5.1 · p. 8

Hard-to-Color Instances for DSATUR

• On the Spinrad–Vijayan family, DSATUR may use n colors for a graph with 3n − 4 vertices and chromatic number 3.The adversarial coloring sequence makes DSATUR assign distinct colors to each of the three vertices associated with each index.Source: Hard-to-Color Instances for DSATUR · pp. 8–9
• The family’s three vertex partitions are independent color classes, providing a 3-coloring against which SSLD’s improvement can be measured.Figure 2 illustrates a graph for which DSATUR uses 5 colors although its chromatic number is 3.Source: Hard-to-Color Instances for DSATUR · p. 9, Figure 2 · p. 9

DIMACS Instances

• DIMACS instances cover random, structured, sparse, and dense cases, including DSJC, flat, queen, myciel, miles, and register-allocation families.The flat family has a known chromatic number, while Mycielski graphs have arbitrarily large chromatic number despite clique number 2.Source: DIMACS Instances · p. 9

Scheduling Instances

• Job-shop instances encode incompatible jobs as adjacent vertices, so a proper coloring gives a feasible schedule and χ(G) is the minimum number of time slots.The evaluation uses COLOR benchmark conflict graphs derived from industrial job-shop problems.Source: Scheduling Instances · pp. 9–10

Frequency Assignment Problems (FAP)

• Frequency assignment is modeled by an interference graph, whose chromatic number equals the minimum number of distinct frequencies required.The evaluation uses CELAR and GRAPH benchmark families derived from French military communication-network planning data.Source: Frequency Assignment Problems (FAP) · p. 10

Random Graphs

• The random-graph evaluation selects Erdős–Rényi, Watts–Strogatz, and Barabási–Albert models.The supplied passages describe the models but do not report a random-graph result comparison.Source: Random Graphs · p. 10

5.2 Results

• Each SSLD result is reported over five independent runs with different random seeds, and the hit count records runs achieving the reported k.The listed flat300 results include hit counts and runtimes for both variants.Source: §5.2 · p. 11, SSLD [D-SDP] SSLD [L-SDP] · p. 11

DSATUR GISD SSLD

• Table 2 lists G5 through G100 with vertex and edge counts, coloring counts, timing values, and hit entries.The supplied table header identifies columns for instance, |V|, |E|, k, t(s), and k (hit).Source: DSATUR GISD SSLD · pp. 12–13

DIMACS benchmark

• Table 3 is identified as the DIMACS benchmark results.Source: Table 3 · p. 12

FAP Instances

• Table 4 reports results for frequency-assignment instances.Source: Table 4 · p. 15

Job Shop Scheduling Instances

• Table 5 reports results for job-shop scheduling instances.Source: Table 5 · p. 15

DSATUR GISD SSLD

• The random-graph comparison covers 1,500 instances across three graph families and reports wins, ties, losses, and color-reduction measures.The passage defines Δavg as the mean color reduction over wins and Δmax as the largest observed improvement.Source: DSATUR GISD SSLD · p. 16, vs DSATUR vs GISD · p. 16

• Each SSLD run combines one SDP solve with T rounding iterations, each using a random projection, greedy independent-set extraction, and DSATUR completion.Source: §5.3 · p. 16
• SDP solve time grows roughly as |V|^2.4, with graph order the strongest structural predictor; the runtime figure plots per-instance solve time against density across benchmark families.The D-SDP's free variables are exactly the non-adjacent vertex pairs.Source: §5.3 · p. 17, Figure 3 · p. 17
• SSLD's median runtime is 0.82 s, versus 4.2 × 10^-3 s for DSATUR, making SSLD 195 times slower.GISD's median runtime is 5.3 × 10^-4 s.Source: §5.3 · p. 17
• At T = 500, rounding takes a median 34.7% of runtime and exceeds the SDP solve on 280 of 1,604 instances (17.5%).The rounding share varies by family, from approximately 0.5% on large FAP instances to 45.3% on small scheduling instances.Source: §5.3 · p. 17, Figure 4 · p. 18
• Against DSATUR, SSLD uses fewer colors on 876 instances, ties on 726, and loses on 2 (mean −0.83 colors); against GISD, it records 988/615/1 (mean −0.94 colors).Source: Figure 5 · p. 18, §5.3 · p. 18

6 Conclusion

• SSLD uses fewer colors than DSATUR on 876 of 1604 instances, ties on 726, and loses on 2; against GISD, it wins on 988, ties on 615, and loses on 1.Across the benchmark categories, SSLD matches or improves on DSATUR in almost every case.Source: §6 · p. 19
• SSLD is roughly 195 times slower than DSATUR in median runtime, while rounding takes a median 34.7% of total runtime and exceeds the SDP cost on 17.5% of instances.Runtime grows with graph size and density, causing timeouts on several CELAR and GRAPH instances.Source: §6 · p. 19
• The D-SDP embedding gives no mathematical guarantee that its extracted independent sets are optimal or good first classes for minimizing DSATUR's completion colors.The formulation encourages alignment of non-adjacent vertices but does not ensure that random projections produce the desired class.Source: §6 · p. 19
• Proposed next steps include guided or optimized projection search, iteratively fixing multiple classes, and improving rounding by combining directions or using the prior coloring.Source: §6 · p. 19
• For large instances, the SDP solve remains the dominant runtime cost; warm starts, sparsity, or a cheaper relaxation are proposed to improve practicality on denser and larger graphs.Source: §6 · pp. 19–20