The maximum k‐colorable subgraph problem and orbitopes

Given an undirected node‐weighted graph and a positive integer $k$ , the maximum $k$ ‐colorable subgraph problem 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 on 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 consequences of combining problem‐specific structure with orbitope structure. We first show that the LP‐bound of the integer programming formulation mentioned above 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 polytope associated with the maximum $k$ ‐colorable subgraph problem and the orbitope remain facet‐defining for the combined polytope or can be modified to yield facets. It turns out that the results depend on both the structure and the labeling of the underlying graph.