# 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 :)

Submitted by nimo on Mon, 2013-05-13 15:10

»

- Login to post comments

## 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.

## 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?