Parameterized Extension Complexity of Independent Set and Related Problems

Logo poskytovatele
Logo poskytovatele

Varování

Publikace nespadá pod Ekonomicko-správní fakultu, ale pod Fakultu informatiky. Oficiální stránka publikace je na webu muni.cz.
Autoři

GAJARSKÝ Jakub HLINĚNÝ Petr TIWARY Hans Raj

Rok publikování 2018
Druh Článek v odborném periodiku
Časopis / Zdroj Discrete Applied Mathematics
Fakulta / Pracoviště MU

Fakulta informatiky

Citace
www http://arxiv.org/abs/1511.08841
Doi http://dx.doi.org/10.1016/j.dam.2017.04.042
Obor Informatika
Klíčová slova parameterized complexity; extension complexity; independent set; FO model checking
Popis 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 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.
Související projekty:

Používáte starou verzi internetového prohlížeče. Doporučujeme aktualizovat Váš prohlížeč na nejnovější verzi.