6

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!

Trivial example for demonstration.

ryecatcher
  • 61
  • 4
  • 1
    could you clarify 4. a bit more? Looks to me like you could color every vertex red, and the answer would be 0, (or if you're not allowed two colors next to each other, then the answer has to be equal to the number of edges between routers) – Rusty Rob May 25 '12 at 02:38
  • @robertking : I should have been clearer. You cannot change/assign the colors of the "cores" (the square vertices in the diagram). In effect you are given a partially colored graph. The objective is to color the rest of it (the routers). Hopefully that is better? – ryecatcher May 25 '12 at 04:11
  • @chris : Yes the underlying "problem" is a network (closest analogy). The connections between the routers (the circles) are bi-directional, effectively making it a cyclic graph. – ryecatcher May 25 '12 at 04:18
  • How come there are red ones next to each other in "Optimal color assignment" – Rusty Rob May 25 '12 at 04:31
  • @robertking : That is allowed. In-fact unless I misunderstood your question that is kind of the objective. In the trivial-est of examples you would have a single router connected to say 2 "cores" each of color red. And then the optimal solution would be simply to paint the router red. – ryecatcher May 25 '12 at 04:34
  • so in the Optimal case, the number of edges between vertices of different colors is 1 (because R1 is connected to a yellow). In the sub-optimal example, the number of edges between vertices of different colors is 2 (because yellow r1 is connected to two red ones). If both R1 and R2 were yellow, the number of edges between vertices of different colors would be 2 because there are two red squares. – Rusty Rob May 25 '12 at 04:49
  • Whats the typical size of an input (number of routes / cores)? Whats the average degree? – Reinhard May 25 '12 at 05:03
  • Can a core connect to multiple routers? or does each core have just one connection? – Rusty Rob May 25 '12 at 05:05
  • @Reinhard : Typical Size .. Routers 5-10 , Cores : 15-30, Degree : 3-7 Max Size .. Routers 20, Cores : 100, Degree 10. robertking : Great question, should have clarified before. A core is connected only to one router. – ryecatcher May 25 '12 at 05:14

2 Answers2

3

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.

Martin Hock
  • 944
  • 4
  • 5
  • Thank you! After having spent some time trying to refresh my graph theory basic, this does make sense and seems like a very interesting way to solve it. Hopefully I will be able to code up the algorithm for the multiterminal cut problem and see how it works out! – ryecatcher May 27 '12 at 04:03
0

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

there are much less than 5^10 options, especially if by default you color every router the most common color, and then just change the color of some of them, backtracking where necessary.

Edit: Also there is a nice Hamiltonian path algorithm you could perhaps adapt to your needs provided there are less than 15 routers. What is the dynamic programming algorithm for finding a Hamiltonian cycle in a graph?

Community
  • 1
  • 1
Rusty Rob
  • 16,489
  • 8
  • 100
  • 116
  • Fair call, something I considered and abandoned not because it wouldnt be fast enough on a one time basis. But because this algorithm runs inside the inner-most loop of a larger program that gets executed between 50k-1million times. I might revisit and actually code up the approach you suggest, especially with the backtracking aspect. But still wondering if there is a known graph problem that this "resolves" to. – ryecatcher May 25 '12 at 05:26
  • I just edited with a link to hamiltonian cycles algorithm. It stores results for all subsets of vertices. You can do similar. – Rusty Rob May 25 '12 at 05:30