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

Question

I am not sure if this is really a "coloring" problem, as it is a assignment / linear programming problem. I also have no experience, so I apologize for any nubo that could follow. But I feel that this problem should have been almost completely solved / investigated before, I just could not find anything by looking at many graph algorithms at http://en.wikipedia.org/wiki/Category:Graph_algorithms . I was hoping some pointers were in the right direction.

The expression-task effectively reduces to:

• There are two types of vertices in a graph: routers and kernels.

• Kernels connect only to routers. Each core connects to only one router. And each has a user-entered / specific "color". (In my particular problem, color is limited to one of 4/5 possible colors). Their color cannot be changed; this is an input parameter. (The kernels are the squares in the image below)

• Routers connect to the cores, as well as to other routers. They do not have a “color” assigned to them. Color assignment is part of the purpose of the program / algorithm. (Routers are the circular vertices in the image below.)

• The goal of the program is to assign colors for each router on the graph so that the number of “intersections” / edges between vertices of different colors is minimized.

(Alternative view: in fact, you are given a graph in which some vertices are colored, while others are not. The goal is to color those that are not such that the number of edges between vertices of different colors is minimized.)

I was able to formulate this (rather poorly confident) as an Integer-Linear-Program and set up a solution / approach using LP-Solve. I also have a heuristic. I would like to know the “correct” / famous / other approaches to solving this ?!

Many thanks!

Answer 1

Let's start by focusing on a two-color case. We can turn this into a st min cut case. The idea is that we have designated s node and at node in the graph and want to divide the remaining nodes into either group s or group t, so that the sum of the weights of the edges between the two groups is minimized. For your version, we have yellow yellow node s and master red node t, and we will place a highly weighted edge exceeding the number of all edges in your original graph between each of the kernels and the corresponding primary color node, while all the original edges are weightless 1 each. High price limits guarantee that we will never illegally repaint any of the cores, as it will be cheaper to move all routers. This problem can be solved in polynomial time using standard algorithms for maximum flow through Max Flow-Min cut. . The best choice depends on your edge and the number of vertices.

In the case of multiple colors, you are trying to solve the "multi-pole cut" problem. This is due to the problem of minimal k-cut , but the standard reference for this problem is the document Complexity of multi-terminal abbreviations (to which the link to k-cut refers indirectly). For more than two colors, apparently if the graph is flat, the problem is still solvable in polynomial time; otherwise it is NP-hard , so you can use your whole program solver, as this is another NP-hard problem.

Answer 2

If the number of colors <= 5 and routers <= 10, then you can use brute force.

there are much less than 5 ^ 10 parameters, especially if by default you are the color of each router the most common color, and then just change the color of some of them, stepping back if necessary.

Edit: There is also a good Hamiltonian path algorithm that you can possibly adapt to your needs if there are less than 15 routers. What is a dynamic programming algorithm for finding a Hamiltonian cycle in a graph?