# 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. May 18 at 21:17

## 2 Answers

When the objective function relies on the weights of edges within the subgraphs (as opposed to edges connecting subgraphs), I believe your problem is equivalent to a quadratic multiple knapsack problem. There seems to be a fair bit of literature on that problem (of all of which I am blissfully ignorant).

• May I extend my question to the case where knapsacks have dependencies among each other. E.g. a couple of knapsacks which together are worth more than another couple. Does this problem exists? May 24 at 10:11
• 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. May 24 at 22:14
• Indeed my reasoning was originally with partition of a graph. It is more intuitive my question by thinking that formulation. Hence, an edge can have a weight varying with the considered solution; namely, it can worth more when connecting two elements of the partition, instead of other twos. May 25 at 9:26

The capacitated max-k-cut formulation models the problem I describe.

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.