Before going into how to solve the partitioned graph coloring problem using integer linear programming (which is the goal of my thesis), I thought it would be a good idea to actually explain what is the partitioned graph coloring problem (or PCP from now on).
Graphs and partitions
First of all, graphs. Formally, a graph is defined as two sets: a set of nodes which compose the graph, and a set of edges between pairs of nodes. For example, the definition for the so-called diamond graph is the following:
G = V,E = 1,2,3,4, (1,2),(2,3),(3,4),(4,1),(1,3)
And a representation for it could be the following:
Diamond graph
While this is the simplest form of a graph, several additions can be made: weights or attributes can be assigned to either nodes or edges; edges can be directed; multiple edges can be allowed between pairs of nodes; etc. The modification we will be dealing with in this scenario is partitioning the graph's nodes. As such, the graph is now defined as three sets: besides the nodes and edges, the set of partitions, where each partition is a non-empty set of nodes such that every node belongs to exactly one partition.
A possible partitioning of the diamond graph previously presented could be the following:
G = V,E,P = 1,2,3,4, (1,2),(2,3),(3,4),(4,1),(1,3), 1,2,3,4
Partitioned diamond graph
Coloring
Having defined the kind of graphs we will be working with, it's time to define the problem itself. The graph coloring problem consists in defining a function that assigns a label (a "color") to each node in the graph, with the restriction that every pair of adjacent nodes must have different colors.
For example, a valid coloring for the diamond graph presented earlier would be the following:
Colored diamond graph
The goal here is to find a valid coloring that uses the minimum possible number of different colors. This value is called the chromatic number of a graph.
Determining if there is a valid k-coloring (coloring that uses exactly k colors) for a particular graph is usually difficult to determine, where difficult implies that it requires a huge computational effort; for those of you with background on CS, this problem is known to be NP-complete.
For .NET fans, it is worth checking the posts that Eric Lippert has been uploading recently on making a backtracking algorithm for the coloring problem using C#.
Partitioned Coloring
The coloring problem has several variants. For example, it might be of interest to minimize the not only the number of different colors used, but also the difference between how many nodes are painted with each color. Or allow that adjacent nodes have the same color, incurring in a penalty in an objective function, if it allows the usage of fewer colors.
In this case, the partitioned graph coloring consists in coloring one node per partition, with the restriction that two adjacent nodes may not have the same color. The difference with the standard coloring is that not all nodes must be colored, only one in each partition.
Going back to our diamond example, by cleverly picking which nodes to color in each partition, we can partition-color the whole graph using a single color:
Coloring of partitioned diamond
Even though not all nodes are to be colored, this variant of the problem is still computationally difficult (NP-complete) to solve. Most approaches to it are heuristic, this is, they do not find the optimal solution, but offer a reasonable one in a reasonable time, as all algorithms that guarantee finding the best solution take too long to execute for large graphs.
Our goal will be to use a technique called integer linear programming to solve this problem, obtaining the exact solution in a reasonable time, for medium-sized instances.