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!
Names are Graph Partitioning and Graph Clustering.
You'll find a lot of papers about these problems, and also some software packages. I like this one in particular, and it's rather recent.