Detailed Information on Publication Record
2018
Parameterized Extension Complexity of Independent Set and Related Problems
GAJARSKÝ, Jakub, Petr HLINĚNÝ and Hans Raj TIWARYBasic information
Original name
Parameterized Extension Complexity of Independent Set and Related Problems
Authors
GAJARSKÝ, Jakub (703 Slovakia, belonging to the institution), Petr HLINĚNÝ (203 Czech Republic, guarantor, belonging to the institution) and Hans Raj TIWARY (356 India)
Edition
Discrete Applied Mathematics, Elsevier Science, 2018, 0166-218X
Other information
Language
English
Type of outcome
Článek v odborném periodiku
Field of Study
10201 Computer sciences, information science, bioinformatics
Country of publisher
Netherlands
Confidentiality degree
není předmětem státního či obchodního tajemství
References:
Impact factor
Impact factor: 0.983
RIV identification code
RIV/00216224:14330/18:00100733
Organization unit
Faculty of Informatics
UT WoS
000447109400007
Keywords in English
parameterized complexity; extension complexity; independent set; FO model checking
Tags
Tags
International impact, Reviewed
Změněno: 16/4/2020 09:57, prof. RNDr. Petr Hliněný, Ph.D.
Abstract
V originále
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.
Links
GA14-03501S, research and development project |
| ||
GA17-00837S, research and development project |
|