Parameterized Extension Complexity of Independent Set and Related Problems

Logo poskytovatele
Logo poskytovatele

Varování

Publikace nespadá pod Ústav výpočetní techniky, 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.

Další info