# Cutting an input graph into partitions of a certain size, minimizing the weight of the edges being removed - Name?

Input: A weighted graph $G = (V, E)$, a maximum size $t$, a number of partitions $k$.

Output: $k$ partitions of $G$, represented by the partitions $P = \{p1, ..,p_n\}$ and the set of cut edges $C \subset E$ which divide $G$ into those partitions. Each partition $p$ is of size $|p| = t$, except the last partition, which is of size $|p|<t$. The weight of the edges cut ($\sum |C_i|$) should be minimised.

Is this a problem that already exists? It seems as if it could be some variation of the k-multicut problem which uses pairs $(s,t)$ that must be separated. Or perhaps it is related to the Max-Flow min-cut theorem. Other things I have looked at are the Partition problem and the Minimum multicut, however none of these have bounds on the size of the partitions that are created.

I would also be interested in finding out the complexity class of the problem. I suspect it is NP-Hard.

Background: I am researching possible ideas for a university undergraduate project, and want to use this problem as a solution to a real world problem. If the problem is sufficiently hard it is a feasible candidate to write a lot about heuristic solutions!