%0 Journal Article
%T Parameterized Extension Complexity of Independent Set
%A Jakub Gajarsky
%A Petr Hlinš§ny
%A Hans Raj Tiwary
%J Computer Science
%D 2015
%I arXiv
%X Let $G$ be a graph on $n$ vertices and $\mathop{\mathrm{STAB}}{}_k(G)$ be the convex hull of characteristic vectors of its independent sets of size at most $k$. It is known that optimizing over $\mathop{\mathrm{STAB}}{}_k(G)$ is $W[1]$-hard and is $FPT$ tractable for graphs of bounded expansion. We show analogous results for the extension complexity of $\mathop{\mathrm{STAB}}{}_k(G)$. In particular, we show that when $G$ is a graph of bounded expansion then $\mathrm{xc}(\mathrm{STAB}{}_k(G))\leqslant \mathcal{O}(f(k)\cdot n)$ for some function $f$. For general graphs we show that there is no function $f$ such that, for all natural numbers $k$ and for all graphs on $n$ vertices, the extension complexity of $ \mathop{\mathrm{STAB}}{}_k(G)$ is at most $f(k)\cdot n^{ \mathcal{O}(1)}.$
%U http://arxiv.org/abs/1511.08841v1