Algorithms for the minimum sum coloring problem: a review

Abstract

The minimum sum coloring problem (MSCP) is a variant of the well-known vertex coloring problem which has a number of AI related applications. Due to its theoretical and practical relevance, MSCP attracts increasing attention. The only existing review on the problem dates back to 2004 and mainly covers the history of MSCP and theoretical developments on specific graphs. In recent years, the field has witnessed significant progresses on approximation algorithms and practical solution algorithms. The purpose of this review is to provide a comprehensive inspection of the most recent and representative MSCP algorithms. To be informative, we identify the general framework followed by practical solution algorithms and the key ingredients that make them successful. By classifying the main search strategies and putting forward the critical elements of the reviewed methods, we wish to encourage future development of more powerful methods and motivate new applications.

1 Introduction

Given a graph G, a proper k-coloring of G is an assignment of k different colors $\{1, \ldots , k\}$ to the vertices of G such that two adjacent vertices receive two different colors. The classical graph vertex coloring problem (GCP) is to find a proper (or legal) k-coloring with the minimum number of colors $\chi (G)$ (i.e., the chromatic number of G) for a general graph G. The minimum sum coloring problem (MSCP) is a variant of the GCP and aims to determine a proper k-coloring while minimizing the sum of the colors assigned to the vertices. MSCP was proposed by Kubicka (1989) in the field of graph theory and by Supowit (1987) in the field of VLSI design. MSCP has applications in VLSI design, scheduling and resource allocation for instance (Bar-Noy et al. 1998; Bonomo et al. 2015; Kroon et al. 1996; Malafiejski 2004; Sen et al. 1992). MSCP is also related to other generalizations or variants of GCP like sum multi-coloring (Bar-Noy et al. 1999), sum list coloring (Berliner et al. 2006) and bandwidth coloring (Johnson et al. 2008).

Like the classical vertex coloring problem, MSCP is notable for its practical applicability and theoretical intractability. Indeed, in the general case, the decision version of MSCP is NP-complete (Kroon et al. 1996; Kubicka 1989) and approximating the minimum color sum within an additive constant factor is NP-hard (Kubicka et al. 1991). As a result, MSCP is a computationally challenging problem and any algorithm able to determine the optimal solution of the problem is expected to require an exponential complexity. Due to its high computational complexity, polynomial-time algorithms exist only for some special cases of the problem (see Sect. 3) and solving the problem in the general case remains an imposing challenge.

In the past several decades, much effort has been devoted to developing various approximation algorithms and practical solution algorithms. Approximation algorithms aim to provide solutions of provable quality while practical solution algorithms try to find sub-optimal solutions as good as possible within a bounded and acceptable computation time. The class of heuristic and metaheuristic algorithms has been mainly developed since 2009 and has enlarged our capacity of finding improved solutions on the benchmark graphs. Representative examples of the existing heuristic algorithms include greedy algorithms (Li et al. 2009; Moukrim et al. 2010), tabu search (Bouziri and Jouini 2010), breakout local search (Benlic and Hao 2012), iterated local search (Helmar and Chiarandini 2011), ant colony (Douiri and Elbernoussi 2012), genetic and memetic algorithms (Douiri and Elbernoussi 2011; Jin and Hao 2016; Jin et al. 2014; Kokosiński and Kwarciany 2007; Moukrim et al. 2013; Wang et al. 2013) as well as heuristics based on independent set extraction (Wu and Hao 2012, 2013).

To the best of our knowledge, there is only one review published one decade ago in 2004 (Kubicka 2004) that focuses on polynomial-time algorithms for specific graphs, MSCP generalizations (or variants) and applications. For the purpose of solving MSCP, the first studies essentially concerned the development of approximation algorithms and simple greedy algorithms. Research on practical solution algorithms of MSCP was relatively new and appeared around 2009. Nevertheless, important progresses have been made since that time. The purpose of this paper is thus to provide a comprehensive review of the most recent and representative MSCP algorithms. To be informative, we identify the general framework followed by the existing heuristic and metaheuristic algorithms and their key ingredients that make them successful. By classifying the main search strategies and putting forward the critical elements of the reviewed methods, we wish to encourage future development of more powerful methods and motivate new applications.

In the following sections, we first provide a general definition of MSCP, then a brief introduction of approximation algorithms in Sect. 3, followed by the presentation of the studied heuristics and metaheuristics in Sect. 4. Section 5 presents lower and upper bounds. Before concluding, Sect. 6 introduces MSCP benchmark instances and summarizes the computational results reported by the best performing algorithms on these instances.

2 Definitions and formulation of MSCP

Let $G=(V,E)$ be a simple undirected graph with vertex set $V={\{v_1,\ldots ,v_n\}}$ and edge set $E \subset V \times V$. A proper k-coloring c of G is a mapping $c: V \rightarrow {\{1, \ldots , k\}}$ such that $c(v_i) \ne c(v_j)$, $\forall {\{v_i, v_j\}} \in E$. Equivalently, a proper k-coloring can be defined as a partition of V into k mutually disjoint independent sets (or color classes) $V_1, \ldots , V_k$ such that $\forall u, v \in V_i$ $(i=1, \ldots , k), {\{u, v\}} \notin E$. The objective of MSCP is to find a proper k-coloring c with a minimum sum of the colors that are assigned to the vertices of V. The minimum sum of colors for MSCP is called the chromatic sum of G, and is denoted by $\sum (G)$. The strength s(G) of a graph G is the smallest number of colors over all optimal sum colorings of G. Obviously, the chromatic number $\chi (G)$ of G from the classical vertex coloring problem is a lower bound of s(G), i.e., $\chi (G) \le s(G)$.

Let $\mathscr {C}(G)$ be the set of all proper k-coloring of G and the minimization objective f(c) ($c\in \mathscr {C}(G)$) of MSCP is given by Eq. (1).

$$\begin{aligned} f(c) = \sum _{i=1}^n c(v_i)\quad \ \text {or} \quad \ f(c) = \sum _{l=1}^k l|V_l| \end{aligned}$$

(1)

where $|V_l|$ is the cardinality of $V_l$ and $|V_1| \ge \ldots \ge |V_k|$ with the chromatic sum given by:

$$\begin{aligned} \sum (G) = \min _{c \in \mathscr {C}(G)} f(c) \end{aligned}$$

(2)

Figure 1 shows an illustrative example for MSCP. The graph has a chromatic number $\chi (G)$ of 3 (left figure), but requires 4 colors to achieve the chromatic sum (right figure). Indeed, with the given 4-coloring, we achieve the chromatic sum of 15 while the 3-coloring of left figure leads to a suboptimal sum of 18 (upper bound).

Fig. 1

An illustrative example for MSCP (Jin and Hao 2016). The optimal coloring of the graph leads to an upper bound of the chromatic sum of the graph

As shown in Sen et al. (1992), MSCP can be conveniently formulated as an integer linear programming problem as follows:

$$\begin{aligned} \begin{array}{ll} \text {minimize} &{} g(x)=\sum _{i=1}^n \sum _{l=1}^k l \cdot x_{il}\\ \text {subject to} &{} \left\{ \begin{array}{l} \sum _{l=1}^k x_{il} = 1,\quad i \in \{{1, \ldots , n}\} \\ x_{il} + x_{jl} \le 1,\quad \forall \{v_i, v_j\} \in E, l \in \{{1,\ldots ,k}\} \\ x_{il} \in \{{0, 1}\} \end{array} \right. \end{array} \end{aligned}$$

(3)

where $x_{il} = 1$ ($i \in \{1,\ldots ,n\}, l \in \{1,\ldots ,k\}$) if $v_i$ is assigned color l, $x_{il} = 0$ otherwise.

The first constraint of this ILP model ensures that each vertex receives a single color while the second constraint states that two adjacent vertices cannot be assigned the same color. This linear model can be solved by any ILP solver like CPLEX (Wang et al. 2013). Finally, as shown in Wang et al. (2013), MSCP can also be formulated as a binary quadratic programming model.

3 Polynomial-time and k-approximation algorithms for MSCP

One notes that till now no exact algorithm especially designed for MSCP was reported in the literature except the general solution approach used in Wang et al. (2013) which applies CPLEX to the integer linear programming formulation (Eq. (3)). On the other hand, a number of polynomial-time and k-approximation algorithms have been proposed for specific classes of graphs, such as trees, interval graphs, bipartite graphs, etc (Borodin et al. 2012; Hajiabolhassan et al. 2000; Jiang and West 1999; Kosowski 2009; Malafiejski 2004). These algorithms exploit particular properties of the special graphs considered. In what follows, we briefly recall the main characteristics of these specific classes of graphs:

• A cograph, also called $P_4$-free graph, is a graph that does not contain the path $P_4$ for any four vertices¹;

• $P_4$-reducible graphs are a generalization of cographs where every vertex belongs to at most one $P_4$;

• $P_4$-sparse graphs generalize $P_4$-reducible graphs by imposing that every set of five vertices induces at most one $P_4$;

• Unicyclic graphs contain exactly one cycle;

• A partial k-tree G is a graph with treewidth of at most k, where the treewidth is the size of the largest vertex set in a tree decomposition of G;

• A graph is outerplanar if it is planar (it can be embedded in the plane without crossing edges) and all its vertices lie on the exterior face;

• The line graph L(G) of any graph $G=(V, E)$ is such that its vertex set is E and two vertices of L(G) are adjacent if their corresponding edges in G are incident;

• In an interval graph, each vertex corresponds to an interval (over the set of real numbers for instance) and there is an edge between two vertices if their corresponding intervals intersect.

In the field of VLSI design, Kroon et al. (1996) considered the “optimum cost chromatic partition problem” (OCCP), whose definition is similar to MSCP. For this problem, they introduced a linear-time algorithm for trees (see also Kubicka and Schwenk 1989). Other classes of graph optimally solved in linear time include cographs (Jansen 2000) or unicyclic graphs (Kubicka 2005) for instance.

In Jansen (2000), Jansen found that the OCCP can be solved in polynomial time for partial k-trees. Then, Salavatipour presented a polynomial-time algorithm for $P_4$-reducible graphs (Salavatipour 2003). Furthermore, Bonomo and Valencia-Pabon (2014) studied $P_4$-sparse graphs and found a large sub-family of $P_4$-sparse graphs that can be solved in polynomial time. A cubic algorithm has also been proposed for outerplanar graphs (Kubicka 2005).

Bar-Noy et al. (1998) proposed a 2-approximation algorithm² for line graphs and showed a $(\Delta + 2) /3$-approximation algorithm for graphs with maximum degree $\Delta$. Then, Bar-Noy and Kortsarz (1998) proposed a 10/9-approximation algorithm for bipartite graphs. This approximation ratio was next improved to 27/26 by Malafiejski et al. (2004) which is the best ratio for bipartite graphs to our knowledge. For interval graphs, Nicoloso et al. (1999) presented a 2-approximation algorithm, the best known ratio for this class of graphs being 1.796 (Halldórsson et al. 2003). Let us finally mention a 2-approximation algorithm for the entire class of $P_4$-sparse graphs (Bonomo et al. 2015).

4 Heuristics and metaheuristics for MSCP

Since these approximability results cannot be generalized to an arbitrary graph, for practically solving MSCP in the general case, a number of heuristic and metaheuristic algorithms have been proposed recently. In this section, we review the most representative and effective MSCP heuristic and metaheuristic algorithms which belong to three large classes of methods: greedy algorithms, local search heuristics, and evolutionary algorithms. For each reviewed algorithm, we identify its key ingredients, and highlight if the search process is constrained in the feasible space or is allowed to visit infeasible regions. We also provide in Table 1 a summary of the reviewed algorithms as well as indicators about their performances.

4.1 Greedy algorithms

Greedy algorithms are among the first heuristics proposed for MSCP. These algorithms are generally fast, simple, and easy to implement. Nevertheless, they usually achieve results of poor quality. On the other hand, given their particular features (speed and simplicity), they can advantageously be integrated into other more elaborated approaches where the greedy heuristic is used to generate an initial solution and seeds the search process. For instance, they can be used to provide initial upper bounds for an exact algorithm or to build the initial solution(s) for local search heuristics and evolutionary algorithms.

Table 1 Main heuristic and metaheuristic algorithms for MSCP

Two families of greedy algorithms for MSCP are proposed in Li et al. (2009): MDSAT(n) and MRLF(n). They are based on the two well-known greedy coloring heuristics DSATUR (Brélaz 1979) and RLF (Leighton 1979).

The original DSATUR heuristic employs the saturation degree dsat of a vertex³ as the selection criterion to dynamically determine the next vertex to color. MDSAT(n) improves DSATUR by considering the impact of coloring a vertex where the impact is measured based on the number of vertices whose dsat would (not) be changed. The original RLF heuristic follows the partition perspective of a vertex coloring. It colors as many non-adjacent vertices as possible with one color before going to another color. MRLF(n) which extends RLF is based on the idea of selecting the next candidate vertex v for coloring such that it reduces the chance of using a new color next and keeps the current color class as large as possible. To achieve this goal, MRLF(n) implements sophistic greedy rules which rely on the cardinality of a subset of uncolored vertices that could be colored with and without using a new color.

A more complicated greedy heuristic (EXSCOL) is proposed in Wu and Hao (2012, (2013). It is based on independent set extraction and is highly effective for hard and large graphs. At each iteration, EXSCOL first identifies an independent set S as large as possible by using a tabu search procedure. Secondly, it searches as many independent sets as possible of the same size |S| to build a pool of candidate independent sets. Then, EXSCOL determines a maximum number of disjoint independent sets by solving a maximum set packing problem. Finally, the vertices of each extracted independent set receive the same smallest available color to form a color class. The above process is repeated until the graph becomes empty. Notice that there is no procedure to reconsider the extracted independent sets such that it is impossible for EXSCOL to attain an optimal solution once a “bad” independent set has been extracted.

4.2 Local search heuristics

Local search (or neighborhood search) heuristics progressively modify a candidate solution c by local transformations until a stop condition is reached (Gendreau and Potvin 2010). The two key components of a local search procedure are the evaluation function and the move (or transformation) operator which are defined on a given search space.

The evaluation function is used to assess the quality of a given coloring. The existing MSCP algorithms employ one of two types of evaluation function according to whether feasible or infeasible colorings are visited. For algorithms that explore only feasible solutions (i.e. proper colorings), the minimization function f (i.e., the sum of colors, Eq. (1)) of the MSCP problem is directly used. On the other hand, algorithms that visit both feasible and infeasible solutions usually call for an augmented evaluation function $f_p$ which combines the objective function f and a penalty function p.

In local search algorithms, one iteratively uses one or more move operators to transform the incumbent solutions c to generate new neighboring solutions $c^{\prime }$. The set of neighboring solutions that can be reached by applying a move operator (mv) to the current solution forms the neighborhood (denoted by $N_{mv}$). We describe the commonly used operators as follows.

• One-move changes the color of a vertex in the current solution by moving a vertex v from its current color class $V_i$ to another color class $V_j$ ($i \ne j$). This operator can generate both proper or improper colorings and thus can be used to explore feasible and infeasible regions of the coloring search space;

• Swap displaces a vertex v from its current color class $V_i$ to another color class $V_{j}$ (as One-move) and then moves all adjacent vertices u of v to $V_i$. This operator can generate both proper or improper colorings;

• Exchange swaps a subset of vertices $A \subset V_i$ ($|A|>1$) and another subset of vertices $B \subset V_j$ ($|B|>1$) ($i \ne j$) such that the subgraph induced by $A \cup B$ is a connected component (Jin et al. 2014). The new solution $c^{\prime }$ is feasible (respectively infeasible) if the starting solution c is feasible (infeasible).

In what follows, we classify the representative local search algorithms into two categories according to the adopted neighborhood(s): single neighborhood search and multi-neighborhood search. Since local search can get stuck in local optima, most local search algorithms for MSCP use some diversification techniques to help the search to escape local optima encountered during the search. This is typically achieved by applying one or more perturbation operators to change a local optimum in a random or dedicated way.

4.2.1 Single neighborhood search

The tabu search (TS) algorithm proposed in Bouziri and Jouini (2010) adapts the tabu algorithm designed for the classic vertex coloring problem (Galinier and Hao 1999; Hertz and Werra 1987). It starts with a random coloring and visits both proper and improper colorings with the neighborhood $N_{One-move}$ induced by the One-move operator. If there exist conflicting vertices, TS chooses a best move (according to its evaluation function $f_p$) to change the color of a conflicting vertex. Otherwise, TS picks a (non-conflicting) vertex and change its color at random. The above steps are repeated until a stopping criterion is satisfied. This algorithm relies simply on the tabu list for its diversification and does not call for other perturbation mechanism. This algorithm only showed limited computational results.

The breakout local search (BLS) algorithm described in Benlic and Hao (2012) jointly uses two descent methods and an adaptive multi-perturbation strategy to escape local optima. The basic idea of BLS is to use descent-based local search to discover local optima and employ adaptive perturbations to continually visit different search regions in the search space. BLS explores both feasible and infeasible solutions with the help of the One-move operator. At each iteration, if the current solution c is a feasible coloring, BLS applies a first descent search procedure to attain a local optimum in terms of the objective function f. If c is an infeasible coloring (i.e., with conflicting vertices), BLS applies another descent search procedure guided by an augmented evaluation function which takes into account both the objective function f and the conflicting vertices. BLS is characterized by its adaptive perturbation strategy which, upon the discover of a local optimum, triggers dedicated perturbation operations to escape the local optimum trap. Based on the information on the search state, the perturbation strategy of BLS introduces a varying degree of diversification by dynamically determining the number of perturbation moves to be applied and by adaptively selecting the suitable moves (random or directed perturbations).

4.2.2 Multi-neighborhood search

The MDS(5)+LS algorithm (Helmar and Chiarandini 2011) applies an iterated multi-neighborhood search and also explores feasible and infeasible regions of the search space. It first employs the Swap operator until no further improvement exists in terms of its augmented evaluation function. Note that the obtained solution is not necessarily a proper coloring. If this is the case, MDS(5)+LS switches then to the One-move operator to repair the solution. Additional colors can be used to guarantee that the final coloring is proper at the end of this search phase. Finally, it assigns all the vertices with their smallest legal color and changes the color labels according to the sorted cardinality of the color classes $V_l$ ($|V_1| \ge \ldots \ge |V_k|$). Afterward, a random perturbation operator is applied which consists in moving some vertices from their current color class to another color class at random. This perturbed solution is then used as the starting point of the next round of the search procedure.

4.3 Evolutionary algorithms

Different from local search algorithms which are based on a single solution, evolutionary algorithms use a pool of solutions and try to find gradually better solutions by applying genetic operators (e.g., crossover, mutation, ...) to solutions of the population (Gendreau and Potvin 2010).

The most popular evolutionary algorithms for MSCP follow the hybrid evolution framework called the memetic algorithm which jointly uses a recombination operator and a local search improvement to explore the search space (Gendreau and Potvin 2010). They include, for instance, the MASC algorithm (Jin et al. 2014), MA-MSCP algorithm (Moukrim et al. 2013) and the HESA hybrid search algorithm (Jin and Hao 2016). Besides, an early parallel genetic algorithm PGA (Kokosiński and Kwarciany 2007) employs assignment and partition crossovers, first-fit mutation, and proportional selection without any local search improvement.

The MASC memetic algorithm (Jin et al. 2014) follows the design guidelines of memetic algorithms for discrete optimization (Hao 2012) and combines a multi-parent crossover operator (called MGPX) and a double-neighborhood tabu search procedure. MGPX is a variant of the well-known GPX crossover originally proposed for the classical vertex coloring problem (Galinier and Hao 1999). It builds the color classes of the offspring (which is always a proper coloring) one by one and transmits entire color classes as large as possible until all vertices of the offspring are colored. Besides, the tabu search procedure applies the two different and complementary neighborhoods induced by Exchange and One-move in a token-ring way to find good local optima (according to the objective function f) until the search is stagnating. MASC employs a dedicated perturbation operator to diversify the search. MASC only explores the feasible search space of MSCP.

MA-MSCP is another hybrid genetic algorithm (Moukrim et al. 2013) that also focuses on the feasible search space. It includes a two-parent crossover operator (yet another adaptive variant of GPX (Galinier and Hao 1999)), a hill-climbing local search algorithm and a “destroy & repair” procedures. During the local search phase, the hill-climbing procedure is first applied to improve the current solution by using the One-move operator. To escape local optima, MA-MSCP then applies the “destroy & repair” strategy, which randomly removes some vertices and re-inserts each of them into its largest available color class while keeping the solution feasible. If there is no such a color class, the vertex is moved to a new color class. MA-MSCP employs the above two procedures alternately until no further improvement can be obtained.

HESA is also a hybrid search algorithm (Jin and Hao 2016) that alternates between feasible and infeasible regions of the search space. HESA relies on a double-crossover recombination method and an iterated double-phase tabu search procedure. The recombination method jointly uses a diversification-guided crossover and a grouping-guided crossover to generate promising offspring solutions. During the double-phase tabu search procedure, it first checks if the given solution c is a proper coloring. If c is proper, the first tabu search is called to improve its sum of colors. Otherwise, another tabu search is used to attain a proper coloring which is further improved by the first tabu search to obtain a better sum of colors. The double-phase tabu search only explores the $N_{\text {One}\hbox {-}\text {move}}$ neighborhood. For the purpose of search diversification, HESA applies a conditional mixed perturbation strategy: (1) apply the Swap operator to a randomly chosen vertex to transform the incumbent solution, or (2) replace the current solution by the last local optimum.

Table 1 summarizes the reviewed existing heuristic algorithms with their main characteristics including the type of search paradigm, the neighborhood(s) and the presence or absence of a perturbation strategy together with a comment on their relative performance.

Finally, we mention the BQP-PR evolutionary algorithm (Wang et al. 2013) which relies on a binary quadratic programming formulation of the problem (see Sect. 2) and combines a path relinking approach with a tabu search procedure.

5 Bounds for MSCP

We will refer here to “theoretical” (lower and upper) bounds if they are formally proved, see Sect. 5.1. By opposition, “computational” bounds introduced in Sect. 5.2 designate those obtained running approximate algorithms.

5.1 Theoretical bounds

Recall that for any undirected simple graph $G=(V,E)$ with $n = |V|$ vertices and $m = |E|$ edges, the chromatic number $\chi (G)$ is the smallest number of colors needed to color the vertices of G such that a proper k-coloring exists and the chromatic sum $\sum (G)$ is the minimum sum of the colors assigned to all vertices among all proper k-colorings of G. In this section, we list the current known theoretical lower and upper bounds of MSCP according to Kokosiński and Kwarciany (2007), Moukrim et al. (2013) and Thomassen et al. (1989).

$$\begin{aligned}&\sum (G) \le n + m \nonumber \\&\quad \lceil {\sqrt{8m}} \rceil \le \sum (G) \le \left\lfloor \frac{3(m+1)}{2} \right\rfloor \nonumber \\&\quad n+\frac{\chi (G)(\chi (G)-1)}{2} \le \sum (G) \le \left\lfloor \frac{n(\chi (G)+1)}{2} \right\rfloor \end{aligned}$$

(4)

From Eq.(4), one easily observes that the best theoretical lower and upper bounds available for MSCP are respectively $LB_t = \max \left\{ \lceil {\sqrt{8m}} \rceil , n+\frac{\chi (G)(\chi (G)-1)}{2}\right\}$ and $UB_t = \min \left\{ n + m, \left\lfloor \frac{3(m+1)}{2} \right\rfloor , \left\lfloor \frac{n(\chi (G)+1)}{2} \right\rfloor \right\}$.

5.2 Computational bounds

Given that MSCP is to find a proper k-coloring while minimizing the sum of the colors assigned to the vertices, Eq. (1) gives a computational upper bound for MSCP.

Let $G^{\prime } =(V, E^{\prime }) (E^{\prime } \subseteq E)$ be any partial graph of $G=(V,E)$, $\sum (G^{\prime })$ is a lower bound of $\sum (G)$ since any proper coloring of G must be a proper coloring of $G^{\prime }$: $\sum (G) \ge \sum (G^{\prime })$.

Partial graphs considered in the literature to estimate the computational lower bound $f_{LB}$ include bipartite graphs (trees and paths) (Garey and Johnson 1979; Kroon et al. 1996) and cliques (Moukrim et al. 2010; Wu and Hao 2013), while graph decomposition into cliques⁴ provide better bounds according to Moukrim et al. (2010). Let $c = \{S_1, S_2,$ $\ldots , S_k\}$ be a clique decomposition of G, then Eq. (5) gives a computational lower bound for MSCP since there is a single way of coloring any clique $S_l$ (with $|S_l|$ colors) and the sum of colors of $S_l$ is $|S_l|(|S_l| + 1)/2$.

$$\begin{aligned} f_{LB}(c) = \sum _{l=1}^k \frac{|S_l|(|S_l|+1)}{2} \end{aligned}$$

(5)

Figure 2 shows an illustrative lower bound via clique decomposition. We decompose G into six cliques by ignoring some edges of the original graph G and obtain the chromatic sum $\sum (G^{\prime }) = 13$ (right figure). Clearly, this is a lower bound for MSCP while the chromatic sum $\sum (G) = 15$ (left figure).

To obtain a clique decomposition, one popular approach is to find a proper coloring of the complementary graph $\bar{G}$ of G (Helmar and Chiarandini 2011; Jin and Hao 2016; Moukrim et al. 2013; Wu and Hao 2013), since each color class of $\bar{G}$ is a clique of G.

6 Benchmark and performance evaluation

In this section, we first introduce a set of MSCP instances (benchmarks) that are commonly used to assess the performance of MSCP algorithms and then provide indications about the performances of the reviewed MSCP algorithms. Due to many different factors (programming languages, running platforms, experimental protocols...), it is quite difficult to draw definitive conclusions. Nevertheless, we try to provide some useful indications with respect to their performance in terms of best and average results.

Fig. 2

An illustrative lower bound via clique decomposition. The right figure is a clique decomposition of the graph on the left

6.1 Benchmark

There exists a set of 94 frequently used benchmark instances often used for performance evaluation of MSCP algorithms. 58 instances are part of the COLOR 2002–2004 competitions⁵ while the remaining 36 instances come from the second DIMACS challenge.⁶ Compared to the well-known DIMACS instances, the COLOR 2002-2004 instances are relatively easy except the four large “wap” graphs. These instances refer to various topologies and densities, which can be classified into the 13 following types:

• Twelve classical random graphs (DSJC$n.d, n \in \{125, 250, 500, 1\,000\}, d \in \{1, 5, 9\}$);

• Three geometric graphs (DSJR500.d, $d \in \{1c, 1, 5\}$);

• Six flat graphs (flat$300\_\chi \_0$ with $\chi \in \{20, 26, 28\}$ and flat$1000\_\chi \_0$ with $\chi \in \{50, 60, 76\}$);

• Twelve Leighton graphs (le450_$\chi$a, le450_$\chi$b, le450_$\chi$c, le450_$\chi$d, $\chi \in \{5, 15, 25\}$);

• Four latin square graph (latin_sqr_10 and qg.order$\chi$, $\chi \in \{30, 40, 50\}$);

• Two very large random graphs (C2000.5 and C4000.5);

• Fourteen graphs based on register allocation (fpsol2.i.a, inithx.i.a, zeroin.i.a, mulsol.i.b, $a \in \{1, 2, 3\}$ and $b \in \{1, 2, 3, 4, 5\}$);

• Two graphs from the scheduling area (school1 and school1_nsh);

• Twenty four graphs from the Donald Knuth’s Stanford GraphBase (milesn with $n \in \{250, 500, 750, 1000, 1500\}$, anna, david, huck, jean, homer, games120, queen8.12, and queena.a, $a \in \{5, \ldots , 16\}$);

• Five graphs based on the Mycielski transformation (myciela, $a \in \{3, 4, 5, 6, 7\}$);

• Four graphs that have a hard-to-find four clique embedded (mug$n\_a$, $n \in \{88, 100\}, a \in \{1, 25\}$);

• Two “insertion” graphs (2-Insert_3 and 3-Insert_3);

• Four graphs from real-life optical network design problems (wap05, wap06, wap07, and wap08).

Table 2 Main characteristics of MSCP benchmark (94 instances)

Table 2 gives the detailed characteristics of the benchmark graphs. Columns 2–5 and 9–12 indicate the number n of vertices, the number m of edges, the density $d = 2m/n(n-1)$ and the chromatic number $\chi (G)$ of each graph. Columns 6–7 and 13–14 show the best theoretical lower and upper bounds of the chromatic sum ($LB_t$ and $UB_t$ respectively). Italics entries (in all tables) indicate that theoretical upper bounds equal the computational upper bounds while no theoretical lower bound equals the computational lower bound. Note that, since the chromatic number $\chi (G)$ of some difficult graphs are still unknown, we use the minimum k for which a k-coloring has been reported for G in the literature instead of $\chi (G)$ to compute $LB_t$ and $UB_t$ using the $\min / \max$ equations introduced in Sect. 5.1.

6.2 Performance of MSCP algorithms

Based on the benchmark introduced in the previous section, Table 3 (see the “Appendix”) summarizes the computational results of six representative and effective MSCP algorithms presented in Sect. 4: BLS (Benlic and Hao 2012), MASC (Jin et al. 2014), MDS(5)+LS (Helmar and Chiarandini 2011), EXSCOL (Wu and Hao 2012, 2013), MA-MSCP (Moukrim et al. 2013) and HESA (Jin and Hao 2016). Columns 1–3 present the tested graph and its best known lower and upper bounds ($f^b_{LB}$ and $f^b_{UB}$ respectively, in bold face when optimality is proved), the following 18 columns give the detailed computational results of the six algorithms. “–” marks for the reference algorithms mean non-available results. The results in terms of solution quality (best / average lower and upper bounds, $f^*_{LB} / f^a_{LB}$ and $f^*_{UB} / f^a_{UB}$ respectively) are directly extracted from the original papers. Computing times are not listed in the table due to the difference of experimental conditions (platforms, programming languages, stop conditions...). Nevertheless, the second and third lines of the heading respectively indicate the main computer characteristic (processor frequency) and the stop condition to have an idea of the maximum amount of search used by each approach. Note that there is no specific stop condition for EXSCOL since its extraction process ends when the current graph becomes empty. Furthermore, some heuristics can halt before reaching the stop criterion, when a known (lower) bound is reached for instance.

From Table 3, one observes that only HESA reports results for all the 94 graphs of the benchmark. Besides, MDS(5) $+$ LS, EXSCOL, MA-MSCP, and HESA provide lower and upper bounds while BLS and MASC only give an upper bound. Additionally, Fig. 3 provides performance information of each of the six algorithms compared to the best known upper and lower bounds. One observes that no algorithm can reach all the best known results. BLS and MASC attain the best upper bounds for 17 graphs out of the 27 tested graphs and for 56 graphs out of the 77 tested graphs respectively. MDS(5)+LS reaches the best lower (upper) bound for 24 (26) instances out of 38. EXSCOL reaches the best lower and upper bounds for 38 (out of 62 graphs) and 24 (out of 52 graphs) respectively. MA-MSCP reaches the best lower / upper bound for 51 / 53 graphs out of 81. HESA equals the best lower (upper) bound for 86 (85) instances out of 94.

Since the number of tested graphs differs from one algorithm to another, the performance of these algorithms cannot be compared from a statistical viewpoint. However, from Table 3 and Fig. 3, we can roughly conclude that BLS, MASC, MDS(5)+LS, EXSCOL, MA-MSCP and HESA are currently the most effective algorithms for solving the MSCP problem.

Fig. 3

The performance of six representative MSCP algorithms. The y-axis shows the number of graphs for which an algorithm attains a result equal to or worse than the best known reported bound. a Lower bounds. b Upper bounds

From the theoretical and computational bounds reviewed above, we can make the following observations:

• Optimality is proved for 21 instances out of the 94 tested graphs since the best upper bounds are equal to the best lower bounds (see entries in bold in Table 3);

• 12 theoretical upper bounds equal the computational upper bounds while no theoretical lower bound equals the computational lower bound (italics in Tables 2, 3);

• The theoretical upper bounds of queen$a.a~(a \in \{11, 12, 13, 14, 15, 16\})$ are equal to the best computational lower bounds meaning optimal results;

• Table 3 shows that the best computational lower bounds of some easy graphs (myciela, $a \in \{3, 4, 5, 6\}$, for instance) are not equal to the optimal upper bounds (optimality proved with CPLEX (Wang et al. 2013)). Hence, the method of decomposing the graph introduced in Sect. 5.2 is not good enough in some cases and should be improved.

7 Perspectives and conclusion

This review is dedicated to recent approximation algorithms and practical solution algorithms designed for the minimum sum coloring problem which attracted increasing attention in recent years. MSCP is a strongly constrained combinatorial optimization problem which is theoretically important and computationally difficult. In addition to its relevance as a typical model to formulate a number of practical problems, MSCP can be used as a benchmark problem to test constraint satisfaction algorithms and solvers.

Based on this review, we discuss some perspective research directions.

• Evaluation function and search space: as introduced in Sect. 2, the aim of MSCP is twofold: (1) find a proper k-coloring c of a graph and (2) ensure that the sum of the colors assigned to the vertices is minimized. An evaluation function combining these two objectives has been proposed in Helmar and Chiarandini (2011):

  $$\begin{aligned} f^{\prime }(c)= \sum _{l=1}^k l|V_l| + M |E(V_l)| \end{aligned}$$

  where $E(V_l)$ is the set of conflicting edges in $V_l$ and $M > 0$ is a sufficiently large natural number. Since the evaluation function is used to guide the heuristic search process, it would be interesting to design other effective evaluation function based on a better recombination of the two parts of $f'$. Another possibility could be to explore only the feasible graph coloring search space, like in the competitive MASC and MA-MSCP approaches (Jin et al. 2014 and Moukrim et al. 2013), using more effective (multi-)neighborhood structures. Besides, the combination of the above two ingredients in a proper way may lead to improved MSCP algorithms.

• Maximum independent sets extraction: As shown in Sect. 4.1, EXSCOL is a greedy heuristic based on the independent sets extraction that is quite effective for large graphs. Its major deficiency is that it does not include a procedure to reconsider “bad” independent sets that has been extracted. Hence, one possibility is to devise a backtracking procedure when a “bad” independent set has been identified as proposed for the graph coloring problem (Wu and Hao 2012).

• Exact algorithms: There is no exact algorithm especially designed for MSCP except the general approach which applies CPLEX to solve the integer linear programming formulation of MSCP (Wang et al. 2013). However, as shown in Wang et al. (2013), this approach is only applicable to easy DIMACS instances. On the other hand, some exact algorithms for the classical vertex coloring problem successfully solved a subset of the hard DIMACS graphs. Hence, it would be important to fill the gap by designing exact algorithms for MSCP.

To conclude, the minimum sum coloring problem, like the classical coloring problem, is a generic and useful model. Advances in solution methods (both exact and heuristic methods) for these coloring problems will help find satisfying solutions to many practical problems. Given the increasing interest in the sum coloring problem and their related coloring problems, it is reasonable to believe that research in these domains will become even more intense and fruitful in the forthcoming years.

Appendix

For the purpose of completeness, this Appendix, which reproduces and extends the results given in Jin and Hao (2016), shows a performance summary of the six main heuristic algorithms for the set of 94 DIMACS benchmark graphs in terms of the lower and upper bounds of the MSCP problem.

Table 3 The performance of six heuristics and metaheuristics for the lower and upper bounds of MSCP