How to create sets of nodes on a colored graph while cutting as few edges as possible

Question

I'm a programmer not a mathematician so my jargon is terrible and I apologize.

My problem:

I have a graph (relatively sparse) and I've colored all its nodes. There are no edges between nodes of the same color (probably not relevant). I now want to create sets of nodes such that it contains exactly one node of each color. I want to select every set such that in the end there are as few edges that cross between sets as possible.

Solution?:

All I can think of is the obvious approach of partitioning it into sets randomly then iterating through every node and testing every swap from its current set into another set and then counting whether this increases or decreases the number of edge exits. Then when you find the best swap you make the swap. You then repeat until you find no swaps that improve the edge exit count.

Now 1. How do I prove that this will in fact find the optimum solution and not a "local optimum" and 2. How can this be done more efficiently.

I'm sure it's a solved problem already but I don't know how to google for it because it's been so long since I've studied things like this. Any guidance would be very helpful. Thank you.

Answer 1

Solving this problem is NP-complete (and therefore no polynomial-time solution is known), even in the special case where:

• There are only three colors,
• There are $q$ vertices (the same number) of each color,
• We only want to know if the theoretical minimum of edges that cross between sets is possible: $m-3q$, where $m$ is the total number of edges in the graph $G$.

Equivalently, we want to know if it's possible to choose $q$ triples such that each triple forms a triangle in $G$.

This is the PARTITION INTO TRIANGLES problem, which is NP-complete, as shown for instance here, or for an even more specialized case as Proposition 5.1 here.

Solving the problem in more general cases is likely to be even harder. It's possible, however, that a good approximation algorithm exists, which gets close to the minimum number of edges that cross between sets.