The Minimum Sum Coloring Problem (MSCP) is a significant variation of the classic Graph Coloring Problem (GCP) with profound implications for resource allocation and scheduling. While traditional coloring focuses on minimizing the number of colors used, MSCP aims to minimize the total sum of color weights assigned to vertices. Researchers at AAAI-17 introduced a novel algebraic lower bound, $LBM\Sigma$, which leverages graph structural properties to significantly improve the efficiency of solving MSCP.
The Minimum Sum Coloring Problem
In a standard Graph Coloring Problem, the objective is to assign colors to vertices such that no two adjacent vertices share the same color, using the minimum number of colors (the chromatic number, $\chi(G)$). In MSCP, each color $i$ is associated with a weight $i$. The goal is to find a coloring that minimizes the sum of these weights across all vertices.
This problem is particularly relevant in scheduling: if vertices represent jobs and colors represent time slots, minimizing the sum of colors is equivalent to minimizing the average completion time. A counter-intuitive property of MSCP is that an optimal sum coloring might require more colors than the chromatic number. As shown in the figure above, a 3-coloring can achieve a lower sum (11) than the optimal 2-coloring (12).
Methodology: The $LBM\Sigma$ Bound
The researchers developed the $LBM\Sigma$ bound by focusing on "motifs"—sequences of integers representing the sizes of color classes in a valid coloring.
Motifs and Major Motifs
A motif $p = (n_1, n_2, \dots, n_k)$ for a graph with $n$ vertices is a non-increasing sequence where $\sum n_i = n$. Each $n_i$ represents the number of vertices assigned color $i$. The total sum of a coloring is then $\Sigma(p) = \sum_{i=1}^k i \cdot n_i$.
The innovation of $LBM\Sigma$ lies in constraining these motifs using the graph's independence number, $\alpha(G)$. Since each color class must be a stable set (no two vertices are adjacent), the size of any color class $n_i$ cannot exceed $\alpha(G)$. Previous algebraic bounds were often loose because they allowed the first color class to be unrealistically large. By enforcing $n_i \le \alpha(G)$ and distributing remaining vertices into subsequent colors using "major motif" logic, the authors created a much tighter and more realistic lower bound.
Experimental Evaluation and Results
The $LBM\Sigma$ bound was tested on standard DIMACS and COLOR benchmark suites, including random graphs (DSJC), structured graphs (flat), and le450 instances.
Key findings include:
- Improved Lower Bounds: $LBM\Sigma$ provided tighter lower bounds for 29 out of 70 tested instances compared to prior algebraic methods.
- New Optimality Proofs: By matching the new lower bound with existing upper bounds, the researchers proved the optimal MSCP values for four benchmark graphs for the first time:
flat1000-50-0,flat300-20-0,le450-5c, andle450-5d. - Computational Efficiency: Although calculating $\alpha(G)$ is NP-hard, modern maximum clique solvers allow for the efficient computation of $LBM\Sigma$ for many practical instances.
Conclusion
The $LBM\Sigma$ bound represents a significant step forward in solving the Minimum Sum Coloring Problem. By incorporating the independence number into the algebraic formulation of motifs, the researchers provided a tool that effectively prunes the search space for exact algorithms. Future work will focus on integrating this bound into branch-and-bound solvers and developing approximations for $\alpha(G)$ in massive-scale graphs.
Summary updated