Optimization Online


On the Linear Extension Complexity of Stable Set Polytopes for Perfect Graphs

Hao Hu(h.hu***at***uvt.nl)
Monique Laurent(M.Laurent***at***cwi.nl)

Abstract: We study the linear extension complexity of stable set polytopes of perfect graphs. We make use of known structural results permitting to decompose perfect graphs into basic perfect graphs by means of two graph operations: 2-join and skew partitions. Exploiting the link between extension complexity and the nonnegative rank of an associated slack matrix, we investigate the behaviour of the extension complexity under these graph operations. We show bounds for the extension complexity of the stable set polytope of a perfect graph G depending linearly on the size of G and involving the depth of a decomposition tree of G in terms of basic perfect graphs.

Keywords: Extension Complexity, Stable Set Polytopes, Perfect Graphs

Category 1: Linear, Cone and Semidefinite Programming (Linear Programming )

Category 2: Combinatorial Optimization (Graphs and Matroids )


Download: [PDF]

Entry Submitted: 06/23/2017
Entry Accepted: 06/23/2017
Entry Last Modified: 06/23/2017

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 Optimization Society