The Maximum k-Colorable Subgraph Problem and Orbitopes

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.



View The Maximum k-Colorable Subgraph Problem and Orbitopes