- Tight extended formulations for independent set Austin Buchanan (buchanantamu.edu) Sergiy Butenko (butenkotamu.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 Citation: Download: [PDF]Entry Submitted: 09/15/2014Entry Accepted: 09/15/2014Entry Last Modified: 09/30/2015Modify/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 Optimization Online is supported by the Mathematical Optmization Society.