I am trying some methods to solve the graph coloring problem with large data sets. I decided to start off with the total space search but to eliminate certain combinations that are same due to symmetry. So for instance, if we code the color by a natural number, graph coloring 1-2-1-1 is the same as the coloring 2-1-2-2.

I figured that all the colorings from the same symmetry group can be represented by their member which has all the colors first time appearing in the correct order. For instance in the graph 1-2-1-2-4-3 the appearances of colors is 1, 2, 4, 3 which is not in order. So the colorings 1-2-1-1, 2-1-2-2, 3-1-3-3 are all the same as 1-2-1-1 and I do not even allow the others in the search.

In the implementation I go node by node and if at some node in the search $\gamma$ colors appeared so far, I try out only colors $[1, \gamma + 1]$. I testes for some small cases but for larger cases since I am using some data set with best found solutions noted, it seems that better results are possible though I think I am doing the full space search with symmetry applied. My question is why is this happening and where does my solution method skip the combinations. I really tried hard and could not figure it out. It seems to me idea is fine.

Here is the pseudocode of my algorithm. A bit of clarification. Since I am using depth first I edit the original globally defined graph as a solution for each level.

Graph G

find_solution(curr_node = 0, gamma = 1):
  if curr_node == G.node_count:
    # base case
    if colors_used < colors_used(best_coloring):
      best_coloring = G
    for color in [1, gamma]:
      G.nodes[curr_node].color = color
      if is_coloring_ok(G):
        if color == gamma:
          next_gamma = gamma + 1
          next_gamma = gamma

        find_solution(curr_node + 1, next_gamma)
  • $\begingroup$ "why is this happening" - why is what happening? I can't tell what you're asking. "where does my solution method skip the combinations" - this is your algorithm that you invented, and you're not sure what it's doing or how it works? Where did you get the algorithm/pseudocode from? $\endgroup$ – D.W. Nov 8 '16 at 5:20
  • $\begingroup$ I did invent it though I am not sure if it already exists. As far as I can see it is correct and I can not find the mistake. So I am asking others if they can try to find flaw in my logic since I tried hard and could not. "I really tried hard and could not figure it out. It seems to me idea is fine." I think that sentence explained that I only think that it is correct but when running it I do not get the results so I am asking to point out the mistake in the algorithm if you can find it. Your comment is not that useful. $\endgroup$ – itsRAWRtime007 Nov 8 '16 at 17:45

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.