Let $G$ be a graph on $n$ vertices and $mathrm{STAB}_k(G)$ be the convex hull of characteristic vectors of its independent sets of size at most $k$. We study extension complexity of $mathrm{STAB}_k(G)$ with respect to a fixed parameter $k$ (analogously to, e.g., parameterized computational complexity of problems). We show that for graphs $G$ from a class of bounded expansion it holds that $mathrm{xc}(mathrm{STAB}_k(G))leqslant mathcal{O}(f(k)cdot n)$ where the function $f$ depends only on the class. This result can be extended in a simple way to a wide range of similarly defined graph polytopes. In case of general graphs we show that there is {em no function $f$} such that, for all values of the parameter $k$ and for all graphs on $n$ vertices, the extension complexity of $mathrm{STAB}_k(G)$ is at most $f(k)cdot n^{mathcal{O}(1)}.$ While such results are not surprising since it is known that optimizing over $mathrm{STAB}_k(G)$ is $FPT$ for graphs of bounded expansion and $W[1]$-hard in general, they are also not trivial and in both cases stronger than the corresponding computational complexity results.
Download