CODEWITHSUNDEEP
algorithmoptimizationgraph-theory
Tim Hargreaves
Tim Hargreaves

Reputation: 332

Find graph colouring that minimises sum of weights of edges that share vertex colours

Suppose we have a weighted complete graph with n vertices. We want to colour each vertex one of k colours. The cost of any colouring is the sum of the weights of all edges that connect vertices of the same colour.

For my use case, n will be around 20-50. For k = 2, 3 brute force worked fine, but I would ideally like a solution for any k. It is also the case that the graphs I'm dealing with have reasonable sparsity, but again, I would ideally like to solve the general case.

Upvotes: 1

Views: 607

Answers (1)

Erwin Kalvelagen
Erwin Kalvelagen

Reputation: 16772

A first start could be to throw this at a MIQP (Mixed-Integer Quadratic Programming) solver. It can be linearized into a MIP (that is what a solver like Cplex is doing automatically).

min sum( (arcs(i,j),c), w(i,j)*x(i,c)*x(j,c))   (sum over all arcs i<j and colors c)
subject to  sum(c, x(i,c)) = 1 for all nodes i
            x(i,c) in {0,1}

With 50 nodes, weights 25% dense, k=5 it took me a couple of seconds to solve to proven optimality (but can be much more depending on the data; many zero weights make the problem easier). k=3 is slightly more difficult with a run time between 30 and 60 seconds depending on the exact formulation.

The mathematical formulation of the linearization can be found here.

Upvotes: 4

Related Questions