Vertex-Coloring/Assignment to minimize the number of "color crossings"

Question

I am not sure if this is really a "coloring" problem as much as it is an assignment/linear-programming problem. I have zero expertise in either, so pardon any noob-ness that might follow. But I get the feeling that this problem must have almost definitely been solved/investigated before, I just couldnt find anything after looking through many of the graph algorithms on http://en.wikipedia.org/wiki/Category:Graph_algorithms . I was hoping to get some pointers in the right direction.

The "problem-statement" effectively boils down to :

1. There are two types of vertices in the graph : routers and cores.

2. Cores are connected to routers ONLY. Each core is connected only to a SINGLE router. And each has a user-inputed/defined "color". (In my specific problem the color is limited to one of say 4/5 possible colors). Their color cannot be changed, it is an input parameter. (Cores are the squares in the image below)

3. Routers are connected to cores as well as other routers. They do not have a "color" assigned to them. Assigning a color is part of the objective of the program/algorithm. (Routers are the circular vertices in the image below.)

4. The objective of the program is to assign colors to each router in the graph such that the number of "crossings"/edges between vertices of a different colors are minimized.

(An alternative view : In essence you are given a graph where some vertices are colored, others are not. The objective is to color the ones that are not such that the number of edges between vertices of different color is minimized.)

I was able to formulate this (quite poorly I am sure) as an Integer-Linear-Program and have setup a solution/approach using LP-Solve. I also have a heuristic of my own. I would love to know the "proper"/known/other approaches towards solving this?!

Many Thanks!

Answer 1

Let's start by focusing on the case with two colors. We can turn this into an instance of s-t min cut. The idea is that we have designated an s node and a t node in a graph, and that we want to divide the remaining nodes into either the s group or the t group, such that the sum of the edge weights between the two groups is minimized. For your version, we have a master yellow node s and master red node t, and we place a high weighted edge exceeding the count of all edges in your original graph between each of the cores and their corresponding master color node, with all the original edges intact having weight 1 each. The high cost edges ensure that we will never illegally recolor any of the cores as it will be cheaper to move all of the routers. This problem can be solved in polynomial time using standard max flow algorithms via the Max flow-Min cut theorem. The best choice depends on your edge and vertex count.

In the case of multiple colors, you are trying to solve the "multiterminal cut" problem. This is related to the minimum k-cut problem, but the standard reference for this problem is the paper The Complexity of Multiterminal Cuts (which the k-cut article links to indirectly). For more than 2 colors, apparently if the graph is planar, the problem is still solvable in polynomial time; otherwise, it is NP-hard, so you might as well use your integer programming solver as this is another NP-hard problem.