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?

EDIT: 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$ A good place to start might be to look at the literature for the maximum-cut problem, which (as it shouldn't be too hard to convince yourself) is the $k=2$ case of your problem: en.wikipedia.org/wiki/Maximum_cut $\endgroup$ – Gregory J. Puleo Feb 26 at 21:34
  • $\begingroup$ An algorithm for the problem in the paper you linked to could be used to solve your problem as well (briefly: do a binary search on the sum of weights). But it doesn't look like the paper provides such an algorithm, in general. $\endgroup$ – Misha Lavrov Feb 27 at 2:22

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.