Connectivity via convexity: Bounds on the edge expansion in graphs

ABSTRACT:
Convexification techniques have gained increasing interest over the past
decades. We apply a recently developed convexification technique
for fractional programs by He, Liu and Tawarmalani (2024) to the
problem of determining the edge expansion of a graph. Computing the edge
expansion of a graph is a well-known, difficult combinatorial problem that
seeks to partition the graph into two sets such that a fractional objective
function is minimized.
We give a formulation of the edge expansion as a completely positive pro-
gram and propose a relaxation as a doubly non-negative program, further
strengthened by cutting planes. Additionally, we develop an augmented
Lagrangian algorithm to solve the doubly non-negative program, obtaining
lower bounds on the edge expansion. Numerical results confirm that this
relaxation yields strong bounds and is computationally efficient, even for
graphs with several hundred vertices.