# Graph partitioning/cutting problem

Let $$G = (V,E)$$ be an undirected graph, with $$e \in E$$ has positive weight $$w_e$$.

Given a set of integers $$I = \{i_1,\dots,i_n\}$$ such that $$\sum_{k=1}^n i_k = |V|$$. I want to find a partition $$P$$ of $$G$$ of cardinality $$n$$ such that each element of the partition has cardinality corresponding exactly to one of the elements of $$I$$.

The maximization function sums all the edges weights $$w_{(v_1,v_2)}$$ if both $$v_1$$ and $$v_2$$ belong the same subset within the solution - i.e. $$v_1, v_2 \in P_j$$, for any $$P_j \in P$$.

Similarly, the objective function might be minimizing all the weights $$w_{(v_1,v_2)}$$, where $$v_1$$ and $$v_2$$ belong different element of the partition.

My question is whether such a problem has already an official formulation in literature. Or if there is an interesting equivalent problem.

• The question confuses me. I'll take a guess. Are you looking for the max-k-cut problem? Goldschmidt, O., & Hochbaum, D. S. (1994). A polynomial algorithm for the k-cut problem for fixed k. Mathematics of operations research, 19(1), 24-37. Closely related is correlation clustering: Demaine, E. D., Emanuel, D., Fiat, A., & Immorlica, N. (2006). Correlation clustering in general weighted graphs. Theoretical Computer Science, 361(2-3), 172-187. – ktnr May 18 at 17:47
• Thank you. It is actually almost equivalent to a the capacitated max-k-cut problem. – Daniele Cuomo May 18 at 21:17

• I'm not sure how to interpret that. In what I had in mind, the $k$-th knapsack would have capacity $i_k$, and $\sum_k i_k = \vert V \vert$ would imply that all knapsacks must be used (and filled to capacity). So I do not understand what you have in mind for knapsack dependencies. – prubin May 24 at 22:14
Besides, it is less constraining, since the equality $$\sum_{k=1}^n i_k = |V|$$ becomes $$\sum_{k=1}^n i_k \geq |V|$$, where elements $$i_k$$ are referred as capacity.