# Is there a name for this problem?

Consider a graph $$G = (V,E)$$ where $$V$$ is the set of vertices and $$E$$ is the set of weighted edges. We want to create $$N$$ disjoint subsets of $$V$$ such that the sum of weights inside each subset is maximised whereas the sum of weights that are connecting two different subsets is minimised. The $$N$$ needs to be determined and it's not given upfront. It's part of the solution.

For example, given a graph $$G$$ with 5 vertices. I decide to split into two parts the first one contains vertices 1,2 and 3 and the second one contains 4 and 5. My split maximises the sum of weights on green edges and minimises the sum of weights on red edges

Notice that the number $$N$$ of subsets is part of the decision.

Is this a well-defined optimization problem? It's some variation of a graph partitioning problem, but Is there a more precise name that commonly used name for it? Is there some papers about solving it?

• Are the weights nonnegative? Is there any restriction on $N$? Aug 28, 2023 at 0:42
• There is no restriction on $N$. Your question on the weights is interesting. I am interested to see your answer in both cases: weights in $\mathbb{N}$ and $\mathbb{Z}$ Aug 28, 2023 at 1:19
• If the weights are nonnegative, take $N=1$, with the entire vertex set $V$ in one part. Aug 28, 2023 at 1:26
• Ok you're right, I think it needs to be $N>1$. Let's assume that weights are non negative, the worst case is when $N = |V|$. All edges are connecting different subsets. Aug 28, 2023 at 2:01
• This is not far from the capacitated clustering problem Aug 28, 2023 at 6:04

What you are looking for sounds like a variant of the HUB-location allocation problem, specifically, Uncapacitated Multiple Allocation Hub Location Problem. This problem contains a graph $$G = (V, E)$$ where there are some disjoint subsets or HUBs that need to be located and some demand points that should be allocated to each hub. The number of hubs/disjoint subsets may be either predetermined or a decision variable. Also, the objective function can be a single form or also multi-objective. In your case, as the objectives have different directions it seems to be the second form.