Abstrakt
Let G be a graph on n vertices and STAB(k)(G) be the convex hull of characteristic vectors of its independent sets of size at most k. We study extension complexity of 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 xc(STAB(k)(G)) <= O(f(k) . 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 no function f such that, for all values of the parameter k and for all graphs on n vertices, the extension complexity of STAB(k)(G) is at most f (k) . n(O(1)). While such results are not surprising since it is known that optimizing over 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. (C) 2017 Published by Elsevier B.V.