On the maximal error of spectral approximation of graph bisection

DOI10.1080/03081087.2015.1133557zbMath1352.05120arXiv1512.06325OpenAlexW3103323616MaRDI QIDQ3179158

Ludmil T. Zikatanov, John C. Urschel

Publication date: 20 December 2016

Published in: Linear and Multilinear Algebra (Search for Journal in Brave)

Abstract: Spectral graph bisections are a popular heuristic aimed at approximating the solution of the NP-complete graph bisection problem. This technique, however, does not always provide a robust tool for graph partitioning. Using a special class of graphs, we prove that the standard spectral graph bisection can produce bisections that are far from optimal. In particular, we show that the maximum error in the spectral approximation of the optimal bisection (partition sizes exactly equal) cut for such graphs is bounded below by a constant multiple of the order of the graph squared.

Full work available at URL: https://arxiv.org/abs/1512.06325

zbMATH Keywords

Fiedler vectorgraph Laplacianspectral bisection

Mathematics Subject Classification ID

Graphs and linear algebra (matrices, eigenvalues, etc.) (05C50) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Connectivity (05C40)

Cites Work

• Unnamed Item
• Old and new results on algebraic connectivity of graphs
• Graph partitioning by eigenvectors
• A note on Laplacian graph eigenvalues
• Laplacian graph eigenvectors
• Laplacian matrices of graphs: A survey
• Spectral bisection of graphs and connectedness
• A Cascadic Multigrid Algorithm for Computing the Fiedler Vector of Graph Laplacians
• Partitioning Sparse Matrices with Eigenvectors of Graphs
• Parallel Multilevel series k-Way Partitioning Scheme for Irregular Graphs
• On the Optimality of the Median Cut Spectral Bisection Graph Partitioning Method
• On the Quality of Spectral Separators
• A survey of graph laplacians

Related Items (5)

Combinatorial Fiedler theory and graph partition ⋮ Agglomeration of polygonal grids using graph neural networks with applications to multigrid solvers ⋮ On the Structure of Isometrically Embeddable Metric Spaces ⋮ Diffuse Interface Models on Graphs for Classification of High Dimensional Data ⋮ Fiedler vectors with unbalanced sign patterns

This page was built for publication: On the maximal error of spectral approximation of graph bisection