TY - JOUR

T1 - On the maximal error of spectral approximation of graph bisection

AU - Urschel, John C.

AU - Zikatanov, Ludmil T.

N1 - Publisher Copyright:
© 2016 Informa UK Limited, trading as Taylor & Francis Group.

PY - 2016/10/2

Y1 - 2016/10/2

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

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

UR - http://www.scopus.com/inward/record.url?scp=84955167622&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=84955167622&partnerID=8YFLogxK

U2 - 10.1080/03081087.2015.1133557

DO - 10.1080/03081087.2015.1133557

M3 - Article

AN - SCOPUS:84955167622

SN - 0308-1087

VL - 64

SP - 1972

EP - 1979

JO - Linear and Multilinear Algebra

JF - Linear and Multilinear Algebra

IS - 10

ER -