Optimization Online


Tight extended formulations for independent set

Austin Buchanan (buchanan***at***tamu.edu)
Sergiy Butenko (butenko***at***tamu.edu)

Abstract: This paper describes tight extended formulations for independent set. The first formulation is for arbitrary independence systems and has size $O(n+\mu)$, where $\mu$ denotes the number of inclusion-wise maximal independent sets. Consequently, the extension complexity of the independent set polytope of graphs is $O(1.4423^n)$. The size $O(2^\tw n)$ of the second extended formulation depends on the treewidth \tw of the graph, which is a common measure of how tree-like it is. This improves upon the size $O(n^{\tw+1})$ extended formulations implied by the Sherali-Adams reformulation procedure (as shown by Bienstock and Ozbay). This implies size $O(n)$ extended formulations for outerplanar, series-parallel, and Halin graphs; size $2^{O(\sqrt{n})}$ extended formulations for planar graphs; and size $O(1.2247^n)$ extended formulations for graphs of maximum degree three.

Keywords: fixed-parameter tractable extended formulation; treewidth; independent set; extended formulation; stable set polytope; independence system; series-parallel

Category 1: Combinatorial Optimization

Category 2: Combinatorial Optimization (Polyhedra )

Category 3: Network Optimization


Download: [PDF]

Entry Submitted: 09/15/2014
Entry Accepted: 09/15/2014
Entry Last Modified: 09/30/2015

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