Parameterized extension complexity of independent set and related problems

Result code in IS VaVaI
<a href="https://www.isvavai.cz/riv?ss=detail&h=RIV%2F00216208%3A11320%2F18%3A10387251" target="_blank" >RIV/00216208:11320/18:10387251 - isvavai.cz</a>
Alternative codes found
RIV/00216224:14330/18:00100733
Result on the web
<a href="https://doi.org/10.1016/j.dam.2017.04.042" target="_blank" >https://doi.org/10.1016/j.dam.2017.04.042</a>
DOI - Digital Object Identifier
<a href="http://dx.doi.org/10.1016/j.dam.2017.04.042" target="_blank" >10.1016/j.dam.2017.04.042</a>

Result language
angličtina
Original language name
Parameterized extension complexity of independent set and related problems
Original language description
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.
Czech name
—
Czech description
—

Type
J<sub>imp</sub> - Article in a specialist periodical, which is included in the Web of Science database
CEP classification
—
OECD FORD branch
10201 - Computer sciences, information science, bioinformathics (hardware development to be 2.2, social aspect to be 5.8)

Project
Result was created during the realization of more than one project. More information in the Projects tab.
Continuities
P - Projekt vyzkumu a vyvoje financovany z verejnych zdroju (s odkazem do CEP)

Publication year
2018
Confidentiality
S - Úplné a pravdivé údaje o projektu nepodléhají ochraně podle zvláštních právních předpisů

Similar results(10)