Under the auspices of the Computational Complexity Foundation (CCF)

REPORTS > KEYWORD > INDEPENDENT SET POLYTOPES:
Reports tagged with Independent set polytopes:
TR16-070 | 24th April 2016
Mika Göös, Rahul Jain, Thomas Watson

Extension Complexity of Independent Set Polytopes

Revisions: 1

We exhibit an $n$-node graph whose independent set polytope requires extended formulations of size exponential in $\Omega(n/\log n)$. Previously, no explicit examples of $n$-dimensional $0/1$-polytopes were known with extension complexity larger than exponential in $\Theta(\sqrt{n})$. Our construction is inspired by a relatively little-known connection between extended formulations and (monotone) circuit ... more >>>

ISSN 1433-8092 | Imprint