On bounding the bandwidth of graphs with symmetry

Understand

We derive a new lower bound for the bandwidth of a graph that is based on a new lower bound for the minimum cut problem.

• Our new semidefinite programming relaxation of the minimum cut problem is obtained by strengthening the known semidefinite programming relaxation for the quadratic assignment problem (or for the graph partition problem) by fixing two vertices in the graph; one on each side of the cut.
• This fixing results in several smaller subproblems that need to be solved to obtain the new bound.
• In order to efficiently solve these subproblems we exploit symmetry in the data; that is, both symmetry in the min-cut problem and symmetry in the graphs.