1
$\begingroup$

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!

$\endgroup$
1
$\begingroup$

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.

$\endgroup$

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.