  


The Maximum kColorable Subgraph Problem and Orbitopes
Tim Januschowski (januscs.ucc.ie) Abstract: Given an undirected nodeweighted graph and a positive integer k, the maximum kcolorable subgraph probem is to select a kcolorable 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 branchandcut 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 LPbound of the above mentioned integer programming formulation can only be slightly improved by adding a complete orbitope description. We therefore investigate several classes of facetdefining inequalities for the polytope obtained by taking the convex hull of feasible solutions for the maximum kcolorable subgraph problem that are contained in the orbitope. We study conditions under which facetdefining inequalities for the two basic polytopes remain facetdefining 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 ) Citation: Download: [PDF] Entry Submitted: 11/16/2010 Modify/Update this entry  
Visitors  Authors  More about us  Links  
Subscribe, Unsubscribe Digest Archive Search, Browse the Repository

Submit Update Policies 
Coordinator's Board Classification Scheme Credits Give us feedback 
Optimization Journals, Sites, Societies  