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.

  • 1
    $\begingroup$ 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. $\endgroup$
    – ktnr
    May 18 at 17:47
  • $\begingroup$ Thank you. It is actually almost equivalent to a the capacitated max-k-cut problem. $\endgroup$ May 18 at 21:17

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

  • $\begingroup$ 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? $\endgroup$ May 24 at 10:11
  • $\begingroup$ 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. $\endgroup$
    – prubin
    May 24 at 22:14
  • $\begingroup$ 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. $\endgroup$ 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.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.