2015/11/27 by Jakub Gajarský, Gajarský, Jakub, Petr Hliněný +3
Computer Science · #Advanced Graph Theory Research #Complexity and Algorithms in Graphs #Computational Complexity (cs.CC) #F.1.3 #FOS: Computer and information sciences #G.1.6 #G.2.2 #cs.CC #semigroups and automata theory
paper · pdf · doi:10.48550/arxiv.1511.08841
20 pages
openalex publication_date 2015/11/27 · arxiv created 2017/03/07 · arxiv updated 2017/03/08 · openalex created_date 2022/10/02 · openalex updated_date 2026/07/28
Let G be a graph on n vertices and STABk(G) be the convex hull of characteristic vectors of its independent sets of size at most k. We study extension complexity of STABk(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(STABk(G))\leqslant 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 \em no function f such that, for all values of the parameter k and for all graphs on n vertices, the extension complexity of STABk(G) is at most f(k)⋅ nO(1). While such results are not surprising since it is known that optimizing over STABk(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.