Given an undirected node-weighted graph and a positive integer k, the maximum k-colorable subgraph probem is to select a k-colorable induced subgraph of largest weight. The natural integer programming formulation for this problem exhibits a high degree of symmetry which arises by permuting the color classes. It is well known that such symmetry has negative effects of the performance of branch-and-cut algorithms. Orbitopes are a polyhedral way to handle such symmetry and were introduced in Kaibel and Pfetsch [2008]. The main goal of this paper is to investigate the polyhedral interaction of problem specific with orbitope structure. We first show that the LP-bound of the above mentioned integer programming formulation can only be slightly improved by adding a complete orbitope description. We therefore investigate several classes of facet-defining inequalities for the polytope obtained by taking the convex hull of feasible solutions for the maximum k-colorable subgraph problem that are contained in the orbitope. We study conditions under which facet-defining inequalities for the two basic polytopes remain facet-defining for the new one or can be modified to do so. It turns out that the results depend on both the structure and the labeling of the underlying graph.

## Article

Download

View The Maximum k-Colorable Subgraph Problem and Orbitopes