Optimization Online


The Maximum k-Colorable Subgraph Problem and Orbitopes

Tim Januschowski (janus***at***cs.ucc.ie)
Marc Pfetsch (m.pfetsch***at***tu-bs.de)

Abstract: 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.

Keywords: combinatorial optimization, integer programming, symmetry breaking, coloring

Category 1: Combinatorial Optimization (Polyhedra )

Category 2: Integer Programming (Cutting Plane Approaches )


Download: [PDF]

Entry Submitted: 11/16/2010
Entry Accepted: 11/16/2010
Entry Last Modified: 03/16/2011

Modify/Update this entry

  Visitors Authors More about us Links
  Subscribe, Unsubscribe
Digest Archive
Search, Browse the Repository


Coordinator's Board
Classification Scheme
Give us feedback
Optimization Journals, Sites, Societies
Mathematical Programming Society