1. Connectivity via convexity: Bounds on the edge expansion in graphs
- Author
-
Hrga, Timotej, Siebenhofer, Melanie, and Wiegele, Angelika
- Subjects
Mathematics - Optimization and Control - Abstract
Convexification techniques have gained increasing interest over the past decades. In this work, 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 program 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., Comment: 35 pages
- Published
- 2024