newbie question: can a vertex be pinned to a fixed partition?

Hey, I'm looking for a MIN-CUT partitioning software, plus one of the requirements is to pin certain vertice to a fixed partition. I used Metis a couple of years ago for its MIN-CUT functionality. But from the manual, Metis doesn't seem to have support to fulfill the requirement of putting some vertice to fixed partitions. Do I miss something? Or is there any way to achieve this using Metis? Thanks!


RE: Metis does not support this

Metis does not support this functionality. However. hMetis does and can be used to compute the min-cut partitioning.

RE: Another question on Metis: what size is good?

From a previous post I found a statement of Metis as "Metis's heuristic algorithms have been optimized for partitioning large unstructured graphs and they almost always fail to produce good solutions for relatively simple problems."

In my case, the size of the graph is about tens to a couple of hundreds vertice, and the resulting partition is < 4. And I'm looking for MIN-CUT. Should Metis be good for problems of such size? Thanks!

RE: I suggest you use hMetis for

I suggest you use hMetis for problems of this size.

RE: still about sizes?

What sizes are good for Metis? And what sizes are good for hMetis?

How many partitions are good for Metis? And hMetis?

Many thanks again!

RE: to trick Metis to support this?

Hey, thank you! The pre-assigned option in hMetis sounds perfect for my requirement. Before this, I was thinking to trick Metis to do so. Do you think if thus also works?

To be more specific, I need to partition the graph with MIN-CUT into 2 to 4 partitions, where two kinds of vertice need to be pre-assigned:

1) In each partition, we make sure there is one and only one special vertex: S0 for part0, S1 for part1, (or S2, S3 if more than 2 partitions);
2) Another set of vertice that need to be pre-assigned to part0.

To achieve the above using Metis, I was thinking FIRST to assign a very big balancing weight to S0, S1 (S2, S3), and 0 weight to all the rest vertice. Thus the balancing paritioning will hopefully put each S vertex to a different partition. Also SECONDLY, to achieve 2), an edge of 0 weight is added between S0 to each and every vertex in the set that has to be pre-assigned to part0, and an edge of a very big weight from each of the other S vertex to each of vertex in this same set. Thus hopefully the MIN-CUT will put this set of vertice together with S0 to part0.

Sorry about writing such a length description.... Your suggestions are really highly appreciated!!

RE: That sounds too complicated

That sounds too complicated to work. Just use hMetis.