Home » Forums » METIS » Graph & Mesh Partitioning

Size of vertex separator

I ran METIS_NodeComputeSeparator to try to compute a minimally sized vertex separator which splits a graph in two approximately equal pieces.

This is a graph with ~7000 nodes. Depending on the parameters I use, METIS's vertex separator is sometimes ~2300 nodes, and sometimes ~1400 nodes. I'm pretty sure that for my particular graph <1000 nodes are needed to form the appropriate vertex separator.

I thought METIS was supposed to construct small vertex separators. Is METIS not suited for my particular task?

(I'm running a version of METIS from 2002, if that's relevant.)

Thanks :)

‹ metis 5.0 on fortran90 - how set options? partitioning on large graphs ›
Submitted by nimo on Mon, 2013-05-13 15:10
»

RE: Use the latest version of

Use the latest version of Metis as it should do much better for this type of graphs. If it does not, send me the graph.

Submitted by karypis on Tue, 2013-05-14 07:18.
»

RE: Ah, my graph is power law,

Ah, my graph is power law, and it appears a different coarsening scheme is needed for power law graphs. Is the improved coarsening scheme from "Multilevel Algorithms for Partitioning Power-Law Graphs" implemented in the most recent version of METIS?

Submitted by nimo on Mon, 2013-05-13 18:59.
»