Armbruster, Michael ; Fügenschuh, Marzena ; Helmberg, Christoph ; Martin, Alexander : On the Graph Bisection Cut polytope

Author(s):

Armbruster, Michael
Fügenschuh, Marzena
Helmberg, Christoph
Martin, Alexander

Title:

On the Graph Bisection Cut polytope

Electronic source:

application/pdf

Preprint series:

Technische Universität Chemnitz, Fakultät für Mathematik (Germany). Preprint 20, 2006

Mathematics Subject Classification:

90C57

[ Polyhedral combinatorics, branch-and-bound, branch-and-cut ]

Abstract:

Given a graph $G=(V,E)$ with node weights $f_v \in \mathbb{N}_0,\, v\in V$, and some number $F\in \mathbb{N}_0$, the convex hull of the incidence vectors of all cuts $\delta(S),\, S\subseteq V$ with $f(S)\le F$ and $f(V\setminus S)\le F$ is called the {\em bisection cut polytope}. We study the facial structure of this polytope which shows up in many graph partitioning problems with applications in VLSI-design or frequency assignment. We give necessary and in some cases sufficient conditions for the knapsack tree inequalities to be facet-defining. We extend these inequalities to a richer class by exploiting that each cut intersects each cycle in an even number of edges. Finally, we present a new class of inequalities that are based on non-connected substructures yielding non-linear right-hand sides. We show that the supporting hyperplanes of the convex envelope of this non-linear function correspond to the faces of the so-called {\em cluster weight polytope}, for which we give a complete description under certain conditions.

Keywords:

polyhedral combinatorics, minimum bisection problem, knapsack tree inequality, bisection knapsack walk inequality, cluster weight polytope

Language:

English

Publication time:

11 / 2006