SAT-boosted Tabu Search for Coloring Massive Graphs

Since the work on graph coloring is extensive, we discuss only the most relevant work for this article. We refer to Sun’s dissertation [35] for a more exhaustive survey on graph coloring algorithms.

Greedy colorings are the most common and easy heuristics for graph coloring. Given an ordering of the vertices, each vertex gets assigned the smallest color that avoids monochromatic edges in the given order. Different heuristics use different orderings. DSatur [5] is one of the most successful greedy heuristics, and we use it in our approach. DSatur always chooses as the next vertex one that is most constrained, i.e., one with the fewest colors available.

Tabu search has been successfully used for graph coloring. Most relevant to this article is Partialcol [4], which we discuss in more detail in Section 2.3.

Iterated-DSatur (I-DSatur) [19] is a SAT-based extension of DSatur that combines DSatur with extensive pre-processing and SAT-solving to a new method that can compute optimal colorings for small graphs. Used as a heuristic, it scales to sparse graphs with several million vertices. I-DSatur adds a reordering mechanism to DSatur invoked whenever the current uncolored vertex v cannot be colored with any of the existing colors, i.e., the current partial k-coloring would become a partial \((k + 1)\)-coloring. At this point, I-DSatur tries to find a better coloring for all the vertices colored so far and v. If successful, then no new color is required; if unsuccessful, then the best lower bound on the number of required colors known to I-DSatur can be increased. The main difference between GC-SLIM and I-DSatur is that GC-SLIM tries to reduce the number of colors by improving several smaller local instances, while I-DSatur tries to find improvements for a single local instance that is as large as possible. The former scales better on dense graphs, while the latter performs better on sparse graphs, as we will further discuss in our experimental evaluation.

Large graphs yield a prohibitively large encoding size when the standard SAT encodings for graph coloring are used. Recently, a new approach based on clause learning has been proposed [16, 18], which can circumvent the size issue for many instances. Here, only those clauses required for a correct solution are added iteratively. This approach is also used in I-DSatur [19].

Much research in recent years focused on very large and sparse graphs. The advantage of sparse graphs is that they can often be colored with a small number of colors relative to their size and are easily reducible to smaller graphs. State-of-the-art approaches use these and other structural properties of sparse graphs to scale to graphs with millions of vertices [25, 32, 37]. We compare GC-SLIM to the most recent such algorithms FastColor [25] and I-DSatur [19].

The top three submissions to the CG:SHOP Challenge 2022 used different variations of the same idea. They perform local search guided by a conflict score, i.e., how often a vertex has been recolored [8, 9, 14, 34]. This strategy performed better on the competition instances than other established local search strategies. We will further discuss this strategy in Section 2.3.

We consider a connected simple graph G with the set of vertices \(V(G)\) and set of edges \(E(G)\). We will often assume without loss of generality that \(V(G) = \lbrace 1,\dots ,|V|\rbrace\). We denote the edge between vertices \(v, w \in V(G)\) by vw or equivalently wv. For \(X\subseteq V(G)\), we denote by \(N_G(X) = \lbrace \,u \;{\mid }\;uv \in E(G)\) with \(v\in X\) and \(u\notin X \,\rbrace\) the neighborhood of X. We write \(N_G(v)\) instead of \(N_G(\lbrace v\rbrace)\) and drop the subscript if G is clear from the context. \(G-X\) denotes the graph \(G^{\prime }\) with \(V(G^{\prime })=V(G)\setminus X\) and \(E(G^{\prime })=\lbrace \,uv\in E(G) \;{\mid }\;u,v \in V(G^{\prime })\,\rbrace\).

For an integer \(k \ge 1\), we denote the set \(\lbrace 1,\dots ,k\rbrace\) by \([k]\). A partial k-coloring of a graph G is a mapping \(c:V(c)\rightarrow [k]\) defined on a set \(V(c)\subseteq V(G)\) such that \(c(u)\ne c(v)\) for every \(uv\in E(G)\) with \(u,v\in V(c)\). If \(V(c)=V(G)\), then c is a full k-coloring or simply a k-coloring of G. ² The chromatic number \(\chi (G)\) of a graph G is the smallest k such that G has a k-coloring. We say a k-coloring is optimal if \(k=\chi (G)\).

For a (partial) k-coloring c of G, we call the integers \([k]\)colors and the sets \(c_\ell (G) = \lbrace \,v \in V(G) \;{\mid }\;c(v) = \ell \,\rbrace\), \(\ell \in [k]\), the color classes of c. Observe that each color class is an independent set of G and that color classes are pairwise disjoint. We also write \(c_0(G)=V(G)\setminus V(c)\) for the set of uncolored vertices and write \(c(v)=0\) for a vertex \(v\in V(G)\setminus V(c)\). We write \(c_\ell\), instead of \(c_\ell (G)\), if G is clear from the context. Since its color classes uniquely determine a partial k-coloring, we will often specify a k-coloring this way. Further, we write \(N_{G,c,\ell }(X) = N_G(X) \cap c_\ell (G)\), the \(\ell\)-colored neighborhood. Whenever G and c are clear from context, we drop the subscript and use \(N_\ell (X)\). The prevalence of a color \(\ell\) is \(|c_\ell |\), and the prevalence of a color \(\ell\) with respect to a vertex v is \(|N_{G,c,\ell }(v)|\). Therefore, a least prevalent color of a k-coloring c in the neighborhood of v is \(\arg \min _{\ell \in [k]} |N_{G,c,\ell }(v)|\).

The graph coloring problem takes an undirected graph G as input; the task is to produce a coloring of G that uses the least possible number of colors. The decision version of the problem takes as input G and an integer k; the task is to decide whether G admits a k-coloring.

The Minimum Partition into Plane Subgraphs Problem (MPPS) takes as an instance a geometric graph G, with vertices \(V(G)\) represented by points in the plane, and edges \(E(G)\) by straight-line connections between vertices. The task is to finda partitioning of E into as few classes \(E_1,\dots , E_k\) as possible, such that each subgraph \(G_i\), with \(V(G_i) = V(G)\) and \(E(G_i) = E_i\), is plane.

In this article, we consider the MPPS problem in terms of graph coloring. There is a natural reduction from the MPPS problem to graph coloring, which reduces an MPPS instance G to the conflict graph \(G^{\prime }\), containing a vertex for each line segment and where two vertices are adjacent if the corresponding line segments intersect. Evidently, G admits a partitioning into k plane subgraphs if and only if \(G^{\prime }\) has a k-coloring.

Tabu search is a very successful local search approach to graph coloring. We use Partialcol’s search strategy [4]. Starting from a (non-optimal) \((k+1)\)-coloring c of the given graph G, Partialcol selects a color \(e \in [k+1]\) to eliminate. The vertices in \(c_e\) are then removed from c and considered uncolored, making c a partial k-coloring. Partialcol now tries to complete c and color the vertices in \(c_0\) by performing swaps: For a partial k-coloring c, a vertex \(v^* \in c_0\), and a color \(\ell \in [k]\), a (color) swap of \(v^*\) to \(\ell\) is obtained from c by setting \(c(v^*) := \ell\), and \(c(w) := 0\) for all \(w \in N_\ell (v^*)\). The swap is a p-swap if \(|N_\ell (v^*)| = p\). Let \(u = |c_0|\) be the number of uncolored vertices before the swap, then \(|c_0| = u + p - 1\) after a p-swap.

In each iteration, the algorithm performs a p-swap with smallest p. The choice of color \(\ell\) for the p-swap is restricted by a \({tabu}\) list for vertex \(v^*\): a list of the colors assigned to \(v^*\) in the last few iterations. This mechanism ensures that vertices do not get re-assigned the same colors within a certain number of iterations and forces the algorithm to explore more of the search space. Figure 1 shows how a series of swaps can empty \(c_0\).

Partialcol terminates if \(c_0 = \emptyset\), in which case c is now a full k-coloring, or when it reaches a prescribed number of iterations. Usually, tabu search is run repeatedly, choosing different colors to eliminate.

Conflict Scores. The winning submissions [8, 9, 14, 34] to the CG:SHOP Challenge are based on heuristic algorithms that utilize a different selection criterion based on the conflict count. For a vertex v, the conflict count \(q(v)\) measures how often v has been removed from \(c_0\) by a swap, i.e., how often v has been colored. Initially, we set \(q(v) = 0\) for all vertices v. The conflict count is then used to calculate a conflict score that is used for picking the next swap. The different submissions calculate the conflict score differently. We follow the approach by Spalding-Jamieson et al. [34] due to its simplicity: For the next swap, the solver picks a random vertex \(v \in c_0\) and swaps it to the color \(\ell\) that minimizes \(\sum _{u \in N_\ell (v)}(1 + q(u)^2)\).

Let G be the input graph and c a partial k-coloring of G. Since G is too large to be encoded as a whole to SAT, we select a subset \(X\subseteq V(G)\), based on a process described in the next subsection, limiting the size of X in terms of a budget parameter b. The goal is now to find a partial k-coloring for the induced subgraph \(G^{\prime }\), with \(V(G^{\prime })=X\) and \(E(G^{\prime })=\lbrace \,uv\in E(G) \;{\mid }\;u,v \in X\,\rbrace\).

However, a newly found k-coloring of \(G^{\prime }\) will, in general, not be compatible with the coloring c of the vertices outside X. We consider the vertices adjacent to X as extra constraints by defining the local instance in terms of the list coloring problem: Let L be a mapping that assigns each vertex \(v\in X\) a set \(L(v)\subseteq [k]\), called the list of v. Here in particular, we letA partial list coloring of \((G^{\prime },L)\) is partial k-coloring \(c^{\prime }\) of \(G^{\prime }\) with the additional property that \(c^{\prime }(v)\in L(v)\) for each \(v\in V(c^{\prime })\). Let \(c \cup c^{\prime }\) denote the partial k-coloring obtained by composing c and \(c^{\prime }\):The following lemma provides an important link between colorings and list colorings:

We note in passing that the list coloring problem is a proper generalization of the graph coloring problem. For instance, graph coloring is fixed-parameter tractable in the graph’s treewidth, while list coloring is W[1]-hard when parameterized by treewidth [11].

Our general aim is to increase the number of colored vertices. Ideally, we would find a full k-coloring for \((G^{\prime }, L)\). While this is often not possible, it turns out that it is still useful to obtain a partial list coloring \(c^{\prime }\) of \((G^{\prime },L)\), which colors all previously uncolored vertices and minimizes the number of newly introduced uncolored vertices.

We achieve this by a slight tweak of the local instance. For all \(v \in X \setminus c_0\), we add 0 to \(L(v)\) and thereby allow them to become uncolored. The problem is now a minimization problem: find a partial list coloring \(c^{\prime }\) for \((G^{\prime }, L)\) that minimizes \(|c^{\prime }_0|\).

We encode the existence of a partial list coloring of \(G^{\prime }\) that minimizes the number of uncolored vertices. To this end, for \(r\le |X|\), we define a propositional formula \(F(G^{\prime },L,r)\) that is satisfiable if and only if \((G^{\prime },L)\) has a partial list coloring \(c^{\prime }\) where \(|c^{\prime }_0| \le r\). We can minimize the number of uncolored vertices by solving \(F(G^{\prime },L,r)\) for different values of r.

The encoding requires one set of variables and two sets of clauses. For each \(v \in X\) and \(\ell \in L(v)\), the variable \(c_{v,\ell }\) is true if and only if \(v \in V(c^{\prime })\) and \(c^{\prime }(v) = \ell\) or \(v\notin V(c^{\prime })\) and \(\ell =0\).

Hence, the first set of clauses encodes that each vertex \(v\in X\) is assigned at least one color \(\ell \in L(v)\) or is set to 0:\(c_{v,0}\) is true if and only if \(v\notin V(c^{\prime })\).

The second set of clauses encodes that adjacent vertices in \(G^{\prime }\) must not have the same color:Note that \(c_{v, 0}\) and \(c_{w, 0}\) can both be true even if \(vw\in E(G)\). Finally, we use a totalizer encoding [2] to express the cardinality constraintThe constraint adds \(\Theta (|X| \cdot \log |X|)\) many variables and \(\Theta (|X|^2)\) many clauses.

In this section, we describe how GC-SLIM constructs local instances for the SAT encoding described in the previous section. Let G be the input graph and c a partial k-coloring of G. Our goal is to select a suitable subset \(X\subseteq V(G)\) that defines our local instance. The overall approach is to start at a single uncolored vertex and perform a breadth-first search among the least prevalent colors in the neighborhoods where the size of X is limited by a budget b and the breadth by a branching factor f.

We first select an uncolored vertex \(v^*\in c_0\). We initially put \(X_0=\emptyset\), \(X_1=\lbrace v^*\rbrace\) and continue computing a chain of sets \(X_0 \subsetneq X_1 \subsetneq \dots \subsetneq X_s\) as long as \(|X_{s}|\le b\). If no further addition is possible, then we stop, as we have found the set \(X=X_s\).

Assume we have constructed \(X_{i}\), \(i\ge 1\). We now construct \(X_{i+1}\) by starting from \(X_{i+1} := X_i\) and incrementally extending \(X_{i+1}\). Let \(S=X_i\setminus X_{i-1}\). For each \(w \in S\), we find the smallest non-empty set \(N_\ell (w), \ell \in [k]\) such that \(N_\ell (w) \cap X_{i+1} = \emptyset\). If \(|N_\ell (w)| + |X_{i+1}| \le b\), we add \(N_\ell (w)\) to \(X_{i+1}\) and in any case, we proceed to the next vertex in S. We repeat this step at most f times, i.e., for each vertex in S, we add at most f colors from the neighborhood of the vertex to finish constructing \(X_{i+1}\).

We observe that \(X\setminus V(c)=\lbrace v^*\rbrace\), i.e., \(v^*\) is the only uncolored vertex in X. Figure 2 illustrates local instance selection on a simple graph.

The goal of the budget b is to keep the size of the local instance small enough such that the SAT solver can solve it within an expected timeout. In practice, the best budget varies greatly with the instance, so we automatically adjust it. Whenever a specified number of consecutive SAT solver calls time out, the budget is decreased, and conversely, whenever the same number of consecutive SAT solver calls return a result, the budget is increased.

We described the process such that we always expand \(X_{i+1}\) using the color \(\ell\) such that \(N_\ell (w)\) is minimal. Alternatively, we can also use the conflict score discussed in Section 2.3. We discuss both options in our experimental section.

In this section, we describe chain propagation, which is a powerful technique that allows us to determine whether we can quickly color a given uncolored vertex \(v^*\) by using a chain, or sequence, of swaps and propagating the impact of the swaps in the chain until hopefully finding a 0-swap. This concept is inspired by s-chain tabu search [28], where chains up to a length s are explored, and by the consideration of a single flat chain in I-DSatur [19], where a chain of 1-swaps is applied within a single iteration whenever available. Another way to view chain propagation is as a lookahead for the actions that Partialcol would perform.

We start with the set of uncolored vertices \(U = \lbrace v^*\rbrace\) and try to empty this set by applying the following rules until either \(U = \emptyset\) or no rule is applicable. Whenever we find a chain of swaps that empties U, we have found a chain that successfully colors \(v^*\). Figure 3 illustrates these rules using our running example.

The immediate goal of local search is finding a 0-swap, as a 0-swap decreases the number of uncolored vertices. The problem with 0-swaps is that they only consider the immediate neighborhood of the vertex.

Therefore, local search may miss possible 0-swaps if they are not included in our local instance or hidden behind larger swaps. We remedy this issue by extending chain propagation beyond 0-swaps and exploring all chains of limited complexity with the goal of coloring \(v^*\).

A slightly more elaborate case prevails when we apply the following rule multiple times, keeping the number of uncolored vertices constant, completed by a final application of Rule 1:

We call such a sequence of rule applications a 1-swap chain, sometimes called a flat chain [19].

Even more powerful but also more costly is a p-swap chain, where \(p\gt 1\) is a fixed constant. It uses the following generalization of Rule 2:

Chain propagation explores the possible chains exhaustively. Bookkeeping is necessary to avoid re-applying the same series of swaps, as this leads to cycles, and consequently, chain propagation may not terminate. Further, we apply the rules in order, as it is faster to explore chains without p-swaps.

Two hyperparameters regulate the complexity of the chains. Since Rule 3 increases the number of uncolored vertices, it is the main factor for the complexity of the chains explored and, therefore, the main factor on the runtime of chain propagation. We limit the applications of the rule in two ways: (i) We limit p and thereby how much the number of uncolored vertices can increase within one rule application, and (ii) we limit how often Rule 3 can be applied within one chain for the same reason. Together, the two hyperparameters regulate how much the number of uncolored vertices can increase within a single chain.

Algorithm 1 combines the main ingredients of GC-SLIM that we have discussed. Initially, we compute a k-coloring c with a heuristic like DSatur and then repeatedly call GC-SLIM with different colors as the elimination goal. Each call either succeeds, reducing the number of colors, or fails, in which case, we restore c to the state it had before a color was removed. For each call, we pick the least prevalent color we have not yet tried as the elimination goal, breaking ties arbitrarily.

In Algorithm 1, GC-SLIM starts with adjusting c according to the given elimination goal and then tries to complete c for a prescribed number of iterations. In each iteration, it picks a vertex \(v^*\) and first tries to color it using chain propagation. If this fails, then the algorithm creates a local instance based on \(v^*\) and tries to color it using the SAT encoding. The number of uncolored vertices in the solution to the local instance is limited to m, where m is the prevalence of the least prevalent color in the neighborhood of \(v^*\). This limit of m ensures that GC-SLIM will not perform worse than a p-swap. If the local instance is (partially) colored successfully, then GC-SLIM proceeds to the next vertex; otherwise, it defaults to a p-swap as Partialcol would perform.

The algorithm contains several hyperparameters, which we will discuss next.

The hyperparameters controlling Algorithm 1 are the iteration limit, the timeout for the SAT solver, and the choice of SAT solver.

The iteration limit controls how much time the algorithm spends on eliminating a single color. Lower iteration limits cause shorter runtimes. Therefore, one can try to eliminate more colors in the same amount of time at the price of possibly missing some improvements: Sometimes GC-SLIM will run many iterations with very few uncolored vertices until eventually finding the 0-swaps that complete the coloring. A low iteration limit will miss these improvements. Omitted in the listing is a mechanism that grants GC-SLIM an extra 10% of the iteration limit whenever the number of uncolored vertices decreases. Thus, GC-SLIM runs as long as it reduces the number of uncolored vertices, no matter the iteration limit.

The timeout for the SAT solver follows a similar tradeoff. Lower values lead to quicker search space exploration by trying many different local instances, while larger values may discover new improvements. While the iteration limit regulates how often GC-SLIM generates a local instance, the timeout for the SAT solver strongly influences the budget for the local instances.

The SAT solver can also impact the performance of GC-SLIM, both in terms of memory usage and speed, and different solvers may perform very differently for different instances.

The hyperparameters from this section, together with the branching factor, budget, and p-limit for chain propagation as discussed above, control GC-SLIM. As we will discuss next, some further options can severely impact GC-SLIM’s performance. We will further explore this impact in our experiments.

In this section, we discuss several minor options that can affect GC-SLIM’s efficiency positively or negatively, depending on the instance. We will explore their effects further in the next section.

Prerun Tabu Search. Partialcol iterations are much faster than GC-SLIM iterations and can often reduce the number of colors quicker, while GC-SLIM can find improvements that Partialcol misses. Running Partialcol for several iterations before starting GC-SLIM tries to take the best from both worlds.

Flexible Vertices. We say that a vertex \(v\in V(G)\) is flexible with respect to a (partial) k-coloring c if \(v\in V(c)\) and there is a color \(\ell \in [k]\setminus \lbrace c(v)\rbrace\) such that \(N_\ell (v) = \emptyset\). Thus, we can change the color of a flexible vertex and still have a (partial) k-coloring. We let \(F_c\subseteq V(G)\) be the set of all vertices that are flexible w.r.t. c. Flexible vertices provide an additional option when choosing a color: Instead of simply choosing the least prevalent color, we redefine the prevalence of a color \(\ell\) as \(|c_\ell \setminus F_c|\) and the prevalence w.r.t. the neighborhood of a vertex analogously. This can lead to a more accurate estimation, since flexible vertices allow immediate 0-swaps. This calculation is heuristical, as adjacent flexible vertices can block each other’s color options, so we actually can only change the color of one of them.

Parallelization. GC-SLIM can run in parallel with minimal synchronization: Each thread runs GC-SLIM, and whenever one thread successfully eliminates a color, GC-SLIM is restarted in each thread with the improved coloring. This introduces the new hyperparameter thread count. Generally, more threads are better, as they enable faster search space exploration. Threads can either try to eliminate different colors, the same colors with different hyperparameter settings, or a mixture of both.

We explore how the different hyperparameter settings change the results in the first set of experiments. We use a base configuration and vary the setting of one parameter at a time. Each run for each instance was limited to seven hours.

As the base configuration, we use a SAT solver timeout of 10 seconds, 300 iterations, no chain propagation, a branching factor for local instances of 3, no multithreading, and no prerun tabu search. We count the instances for which a hyperparameter value finds the best coloring. We also count the instances where it does so uniquely, i.e., no other setting for this hyperparameter found an equally good or better coloring.

SAT Solver Timeout. We try different values for the SAT solver timeout: 5, 10 (default), 30, and 60 seconds. A timeout of 5 seconds finds the best result for 37 of the 44 instances, where it reaches the unique best result on 15 of the instances. The results quickly deteriorate with higher timeouts: While a timeout of 10 seconds finds the unique best result for 4 instances, the higher timeouts achieve the same for only one instance.

A closer look at the number of SAT calls and the size of the local instances explains the results. While local instances contain 1,511 vertices on average with a 5 seconds timeout, they only increase to 1,610 vertices on average with a 60 seconds timeout. This is in stark contrast to the number of SAT calls, which decreases from 13,910 to 6,764. Depending on the instance, 25% to 50% of the SAT calls eventually time out, leading to a significant decrease in the number of possible SAT calls with higher timeouts. Therefore, higher timeouts should be reserved for later stages when lower values fail to find improvements.

Chain Propagation. We use different limits for the maximum size of the swaps in the chains we propagate. We use values of 0 (default), 1, 2, 3, and 5. A limit of 2 achieves the overall best result, reaching the best result on 34 of the 44 instances and the unique best on 18 instances. Limiting the chains to 1-swaps or using no chain propagation at all performs very poorly. Higher limits can be beneficial for some instances, as, for example, a limit of 5 performs slightly better on the Snap instances. This indicates that higher limits might be beneficial for large and very sparse graphs.

Figure 4 shows how chain propagation impacts GC-SLIM for large, dense instances. We can see that the number of improvements over time speeds up significantly and becomes comparable to Partialcol in terms of speed, sometimes surpassing it.

Impact of the SAT solver. We consider Glucose and Cadical as SAT solvers due to good results and their capability for incremental solving. Overall, Cadical achieves the unique best result on 19 of the 44 instances and Glucose on 10. This makes Cadical the best default choice, while Glucose may be better suited for individual instances. Glucose generally performs better on random instances and worse on the other instances in our experiments.

Flexible Vertices. Using flexible vertices does not give a clear advantage in the number of best results. Considering flexible vertices achieves the unique best result on 17 of the instances and not considering them on 14. While this does not seem like a clear advantage, the reduction in colors is significant, up to 100 colors for the instances where it performs better. For instances where it performs worse, the increase in the number of colors is never worse than 6. Considering flexible vertices performs consistently better for the CG instances.

Prerun tabu search. The benefits of running tabu search prior to GC-SLIM are very instance-specific. It achieves consistently better results on the DIMACS and Snap instances and worse results on the random and CG instances. This indicates that this configuration is beneficial for small and sparse graphs. One possible explanation is that the tabu search iterations become slower for dense graphs, reducing the efficiency gain over GC-SLIM.

Conflict Score. Another option is using a conflict score to determine swaps and selecting local instances instead of simply picking the smallest colored neighborhood. This achieves the unique best result for 16 instances, while not using this option gives the unique best result on 15, making its benefits very instance-specific. Using prerun tabu search with the conflict score gives the unique best result on 19 instances, in contrast to 17 instances, where the basic configuration finds the unique best result. It performs consistently bad for the random instances, mixed for the DIMACS instances, and consistently good on the CG and snap instances.

Iteration Limit. We try iteration limits of 100, 300 (default), 500, 1,000, and 5,000. None of the limits performs significantly better than the others, with 500 and higher performing better and 5,000 performing overall best with 7 uniquely best results. While 1,000 iterations is a good default setting, different settings may perform better for different instances. Furthermore, higher iteration limits may be necessary if the number of colors is close to optimal and it becomes harder to eliminate a color.

Branching. We try branching factors of 2, 3 (default), 5, 10, and 15. The overall best is a branching factor of 2, which achieves the best result on 31 of the 44 instances and finds 13 uniquely best instances. The results worsen with higher branching factors, except for the Snap instances, where a branching limit of 10 performs best. This matches the results for chain propagation, where higher limits also perform better for the Snap instances, suggesting that a search focused on breadth over depth may be a generally good strategy for sparse instances.

Initial Node Limit. When creating the local instance, we treat the initial vertex as a special case: Instead of limiting the number of colors we choose, we limit the number of neighbors we add for the initial vertex. This system chooses more different colors if there are many low-prevalence colors and fewer if not. We try limits of 10, 25, 50 (default), 75, and 100.

Each limit leads to the best result on about 16 to 21 instances and a unique best result on 4 to 5 instances. Therefore, there is no discernible good default and choosing the right value always depends on the instance at hand. A pattern similar to chain propagation and the branching limit emerges here: The lower the density, the better a higher initial limit, i.e., more focus on breadth, works.

We use the results from the first experiment to discern a best configuration for each of the four sets of instances; the configurations are shown in Table 1.

In our comparison, we use different GC-SLIM configurations, FastColor, I-DSatur, and Partialcol. Each was run with a 24-hour time limit. We additionally run other methods and use their output as GC-SLIM’s input, i.e., we prerun our own implementations of I-DSatur (IS) and/or Partialcol (PC). Partialcol runs either 7 hours alone or 4 hours together with I-DSatur. We also apply multithreading with 4 threads and varying the configuration parameters using the values shown in Table 1. The multithreading runs for only 6 hours and has twice the memory. The results are in Table 2.

The results show how well GC-SLIM performs on large and dense graphs. On the CG and Random instances, it significantly outperforms FastColor and I-DSatur. Interestingly, for random instances, a Partialcol prerun performs consistently better than any other configuration. For the CG instances, using a portfolio of varied configurations, combining the configurations in Table 1, performs best, and the overall best configuration performs comparatively poorly.

While GC-SLIM also outperforms both algorithms on the small DIMACS instances, it does not come close to reaching the best-known value on almost all instances. This shows that specialized algorithms for these small instances work better.

FastColor and I-DSatur shine on the Snap instances where they benefit from the structure of sparse graphs, which GC-SLIM does not particularly exploit. Still, FastColor, which performs better than I-DSatur, finds the best solution for six of the instances, as does the varied configuration. Note that our goal was not to compare FastColor and I-DSatur, but to compare these approaches to GC-SLIM on various graphs.

The GC-SLIM configurations perform very differently. Figure 5 shows the progression over time for selected instances.

Overall, the results show that a varied configuration is better than a single, tuned configuration. This finding is strengthened by the fact that multithreading incurs an overhead, as each thread has to restart once a color has been eliminated.

The competition used 225 instances in total, separated in different classes, where instances into each class are created by the same process but with different sizes and densities. The instances were created such that then-available graph coloring solvers failed to produce good results. This is supported by the fact that these solvers would have placed very low in the competition [10].

We started our submission by implementing Partialcol. This implementation was run for several days for each instance, and we only started implementing GC-SLIM, when Partialcol failed to find improvements. During that time, we varied and randomized every parameter and decision in our implementation. This gives us the possibility to compare GC-SLIM to these long Partialcol runs in Figure 6. The figure shows that GC-SLIM is able to significantly improve the colorings, even after the long Partialcol runs.

We also have results from a more controlled experiment, where GC-SLIM runs for 24 hours using the best configuration. Figure 7 shows that the final GC-SLIM implementation achieves almost the same results as the results from the long runs of Partialcol and GC-SLIM during development as described above. Our final implementation achieves these results in a fraction of the time. This further shows how well GC-SLIM performs on these instances. Finally, Figure 8 shows the comparison between the best GC-SLIM run and the best results from the competition.