Computing the Edge Expansion of a Graph Using Semidefinite Programmin...

Various properties of a graph or network can each be specified through a single constant. Some of these graph constants can be formulated as a discrete optimization problem. Unfortunately, many of these are NP-hard to compute. For most graph constants, there are specific solvers to compute the exact value given instances of moderate size. In several cases, bounds obtained by semidefinite programming have been proven to be extremely effective.

The edge expansion is a constant for which there is no specific solver yet. This constant gives information about the connectivity of a graph. It is the minimum ratio of the number of edges joining two sets and the size of the smaller set over all possible non-trivial bipartitions of the vertices. The edge expansion of a connected graph is small if there is a bottleneck between two large parts of the graph. Because of this fact, it is used in clustering or network design. There are some heuristics to find a bipartition, like the well-known spectral clustering. This fractional optimization problem does not fit into the typical setting like other constants as the maximum cut.

We propose different strategies to compute the edge expansion efficiently. One is to divide the problem into subproblems of an easier-to-handle type. Another one is to apply Dinkelbach's algorithm for fractional programming. Furthermore, we investigate the conjecture of Mihail and Vazirani, stating that the edge epxansion of the graph from a 0/1-polytope is at least 1, using our techniques.