Other formats:
BibTeX
LaTeX
RIS
@article{1392989,
author = {Gajarský, Jakub and Hliněný, Petr and Tiwary, Hans Raj},
article_number = {SI},
doi = {http://dx.doi.org/10.1016/j.dam.2017.04.042},
keywords = {parameterized complexity; extension complexity; independent set; FO model checking},
language = {eng},
issn = {0166-218X},
journal = {Discrete Applied Mathematics},
title = {Parameterized Extension Complexity of Independent Set and Related Problems},
url = {http://arxiv.org/abs/1511.08841},
volume = {248},
year = {2018}
}
TY - JOUR
ID - 1392989
AU - Gajarský, Jakub - Hliněný, Petr - Tiwary, Hans Raj
PY - 2018
TI - Parameterized Extension Complexity of Independent Set and Related Problems
JF - Discrete Applied Mathematics
VL - 248
IS - SI
SP - 56-67
EP - 56-67
PB - Elsevier Science
SN - 0166218X
KW - parameterized complexity
KW - extension complexity
KW - independent set
KW - FO model checking
UR - http://arxiv.org/abs/1511.08841
L2 - http://arxiv.org/abs/1511.08841
N2 - 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.
ER -
GAJARSKÝ, Jakub, Petr HLINĚNÝ and Hans Raj TIWARY. Parameterized Extension Complexity of Independent Set and Related Problems. \textit{Discrete Applied Mathematics}. Elsevier Science, 2018, vol.~248, SI, p.~56-67. ISSN~0166-218X. Available from: https://dx.doi.org/10.1016/j.dam.2017.04.042.
|
