Are there efficient graph partitioning algorithms with guaranteed upper bounds on the bipartition width in terms of the total number of vertices of the graph, or another non-spectral quantity (diameter, girth, ...), for regular graphs?

Most of the bounds I find in the literature are spectral (like Cheeger inequalities and other bounds on the algebraic connectivity). One could combine these bounds with bounds on the spectrum itself, such as the one in this article, to bound something like the sparsest cut, but this approach provides no guarantees with respect to the actual width of the cut (or maybe it does and it is just not clear to me?).

A (loosely) related upper bound is that the bisection width of cubic graphs with $n$ vertices is at most $(\frac16+\epsilon)n, \epsilon>0$ (from this paper). Are there similar worst-case bounds for heuristic bipartition algorithms?


Your Answer

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

Browse other questions tagged or ask your own question.