  


Tight extended formulations for independent set
Austin Buchanan (buchanantamu.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 inclusionwise 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 treelike it is. This improves upon the size $O(n^{\tw+1})$ extended formulations implied by the SheraliAdams reformulation procedure (as shown by Bienstock and Ozbay). This implies size $O(n)$ extended formulations for outerplanar, seriesparallel, 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: fixedparameter tractable extended formulation; treewidth; independent set; extended formulation; stable set polytope; independence system; seriesparallel Category 1: Combinatorial Optimization Category 2: Combinatorial Optimization (Polyhedra ) Category 3: Network Optimization Citation: Download: [PDF] Entry Submitted: 09/15/2014 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  