5
$\begingroup$

The usual problem of graph partitioning is to split a graph (or a mesh) into two partitions.

According to its Github repository's README file, KaHyPar supports both recursive bisection and direct k-way partitioning.

I suppose that recursive bisection is just a recursive application on the partitions of a graph produced by a partition algorithm which produces two partitions, whereas direct k-way partitioning may not use recursion, but it's simply an algorithm which tries to divide the graph directly into the desired number of partitions.

If this is correct, are there any other differences between the two approaches? If not, what is the difference between the two approaches? By the way, is the terminology consistent throughout the literature?

$\endgroup$
2
$\begingroup$

Your intuition is correct -- a bisection method cuts the (hyper)graph in two, and recursive bisection repeatedly applies this strategy until the desired number of cuts have been made. Direct partitioning on the other hand tries to immediately divide up the graph.

Part of the divide between the two is historical. Some of the earliest successful heuristics for graph partitioning were based on bisection rather than direct partitioning. These bisection methods were based on using the second eigenfunction of the graph Laplacian (the Fielder vector). This technique is called spectral bisection if you want the term to search for. There are also some really nice notes about spectral bisection here. In any case, if the number of partitions is a power of two, you can apply spectral bisection recursively and get a usable (if not necessarily optimal) partition, but for an arbitrary number of partitions it's not immediately obvious how to proceed. Good heuristics for directly partitioning a graph only came later. Many of them built on the ideas behind spectral graph partitioning, i.e. using not just the second but many eigenfunctions of the graph Laplacian.

Nowadays the same core ideas are still used, albeit by borrowing ideas from multigrid methods for linear systems; this is how the underlying algorithm in METIS works.

$\endgroup$
  • $\begingroup$ Thanks for confirming my descriptions. I am already aware of the spectral bisection algorithm and a few others (inertial partition, coordinate bisection, etc), but the distinction between the two terms wasn't nonetheless fully clear. $\endgroup$ – nbro Dec 22 '17 at 17:51
  • 1
    $\begingroup$ An important part of this answer is "power-of-two". Think about how you would try to get three equally sized partitions via repeated bisection -- you can't if each bisection step produces equally sized halves of the original graph (which is what most of the bisection algorithms do). $\endgroup$ – Wolfgang Bangerth Dec 23 '17 at 16:25
  • $\begingroup$ @WolfgangBangerth Yeah, that's correct. $\endgroup$ – nbro Dec 23 '17 at 18:03

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.