I would like to know if the following problem has already been formulated and studied and if yes what is the complexity of it's solution.The problem is:Given an undirected graph G with n vertices v_i with i=1..n, and each v_i can be labeled am integer in V_i, how to label the vertices as to minimize the number edges crossing the different subgraphs defined by the labelling?Notice that the different V_i sets may or may not overlap.Examples are shown below. Next to each node are shown its permitted labels between brackets.Example1:v1[5] -> v2[4] -> v3[1]Here each node can only assume one value so the there is only labelling possible.Example2:v1[5,1] -> v2[4,1] -> v3[1]Here as all nodes can be assigned 1 then if we label all one then we have just one subgraph consisting of the original graph with zero edges crossing the borders to other subgraphs (because there is no other subgraph). So this is the optimal solution in this case.Example3:v1[5,1] -> v2[4,1]-> v3[2]Here the optimal solution is to assign v1 and v2 to label 1 and v3 to label 2.
Solution to graph min multicut problem with per vertice integer set constraint?
graphs;optimization;integer programming;partitions