Graph partitioning/cutting problem

Question

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.

Answer 1

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).

Answer 2

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.