Tight extended formulations for independent set

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.

Article

Download

View PDF