I have a graph in which certain vertices are labeled. I need to assign labels to all of the other vertices in a way that minimizes the number of edges between different-label vertices.

How can I do this efficiently?

  • $\begingroup$ Hi Zach could you provide a bit more context? e.g. in how many groups do you want to partition your graph? (notice that if you partition your graph into one group there are zero inter-partition edges) And if the number of partitions is constant or not is also of relevance. $\endgroup$ – plshelp Oct 2 '20 at 20:33
  • $\begingroup$ @plshelp Any number of partitions. But as I describe in my question, certain vertices are already assigned a partition, and those can't be changed. $\endgroup$ – Zach Oct 3 '20 at 14:36
  • $\begingroup$ Such has been call min-cut. $\endgroup$ – greybeard Oct 3 '20 at 15:03

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.