Computing the Edge Expansion of a Graph Using Semidefinite Programming

Akshay Gupte, Melanie Siebenhofer, Angelika Wiegele*

*Corresponding author for this work

Research output: Chapter in Book/Report/Conference proceedingChapter (peer-reviewed)peer-review

Abstract / Description of output

Computing the edge expansion of a graph is a famously hard combinatorial problem for which there have been many approximation studies. We present two versions of an exact algorithm using semidefi- nite programming (SDP) to compute this constant for any graph. The SDP relaxation is used to first reduce the search space considerably. One version applies then an SDP-based branch-and-bound algorithm, along with heuristic search. The other version transforms the problem into an instance of a max-cut problem and solves this using a state-of-the-art solver. Numerical results demonstrate that we clearly outperform mixed- integer quadratic solvers as well as another SDP-based algorithm from the literature.
Original languageEnglish
Title of host publicationCombinatorial Optimization
Subtitle of host publicationISCO 2024
EditorsAmitabh Basu, Ali Ridha Mahjoub, Juan José Salazar González
PublisherSpringer, Cham
Pages111 - 124
Publication statusPublished - 22 May 2024

Publication series

NameLNCS - Lecture Notes in Computer Science


Dive into the research topics of 'Computing the Edge Expansion of a Graph Using Semidefinite Programming'. Together they form a unique fingerprint.

Cite this