J 2018

Parameterized Extension Complexity of Independent Set and Related Problems

GAJARSKÝ, Jakub, Petr HLINĚNÝ and Hans Raj TIWARY

Basic 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

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
Name: Parametrizované algoritmy a kernelizace v kontextu diskrétní matematiky a logiky
Investor: Czech Science Foundation
GA17-00837S, research and development project
Name: Strukturální vlastnosti, parametrizovaná řešitelnost a těžkost v kombinatorických problémech
Investor: Czech Science Foundation