Cheeger constant

Connectivity via convexity: Bounds on the edge expansion in graphs

  • Timotej Hrga
  • Melanie Siebenhofer
  • Angelika Wiegele
    • Categories Linear, Cone and Semidefinite Programming, Semi-definite Programming Tags , , , ,

    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 … Read more

    Edge expansion of a graph: SDP-based computational strategies

  • Akshay Gupte
  • Melanie Siebenhofer
  • Angelika Wiegele
    • Categories Combinatorial Optimization, Parallel Algorithms, Semi-definite Programming Tags , , , ,

    Computing the edge expansion of a graph is a famously hard combinatorial problem for which there have been many approximation studies. We present two variants of exact algorithms using semidefinite programming (SDP) to compute this constant for any graph. The first variant uses the SDP relax- ation first to reduce the search space considerably. One … Read more