I'm trying to partition a small edge-weighted graph into partitions of a maximum size. (The use case, which may or not be relevant, is partitioning a communication graph of a parallel program to minimize more expensive communication costs.) For example, I may have a graph of 21 nodes and I may want a maximum partition size of 4 nodes per partition (7 total partitions); gpmetis produces a partitioning where one partition has 5 nodes (and another has 3). I've found that the rb (recursive bisection) partitioning scheme tends to work better for smaller graphs, but it doesn't always work.
I'm currently using METIS (the gpmetis tool) to do this and on small graphs it sometimes creates partitions that are larger than what I want. Note that the argument to gpmetis is the number of partitions, not the max nodes per partition.
Questions:
why is this happening? Does METIS produce this outcome because it actually provides a better partitioning despite the imbalance in partition size?
Is there any way to achieve my goal of a max partition size (ideally with METIS but I'm open to using other tools).