I have an undirected graph with weighted edges. I want to color the vertices with a given $k$ colors. Let's assume there is no proper coloring with $k$ colors such that adjacent nodes will always have different colors. I want to find the improper color assignments that would minimize the sum of weights of edges between nodes of the same color.

I have looked through many papers looking at improper coloring algorithms but cannot find this particular variant. This paper looks at something similar, but instead minimizes $k$ given a threshold on the sum of weights. Instead, I want to fix $k$ and minimize the sum of weights. Does anybody know the best approach for this?

Full citation to the paper:

J. Araujo, J.-C. Bermond, F. Giroire, F. Havet, D. Mazauric, R. Modrzejewski, Weighted improper coloring, Research report 7590, INRIA, Sophia Antipolis, 2011.

  • $\begingroup$ Your problem is NP-hard. Are you interested in approximation algorithms? Heuristics? $\endgroup$ – Yuval Filmus Feb 26 at 21:12
  • $\begingroup$ I think you should be able to use binary search on the threshold combined with the techniques of that paper, to get what you want. $\endgroup$ – D.W. Feb 26 at 21:15
  • $\begingroup$ I would be fine with approximations or maybe a greedy algorithm if necessary. $\endgroup$ – Andy Carlson Feb 26 at 21:31
  • $\begingroup$ Do you require some guarantees on the solution quality? Probably metaheuristics would be good on the problem, but can you clarify what you are hoping for more precisely? $\endgroup$ – Juho Feb 27 at 9:15

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.