Parameterized Inapproximability of Independent Set in H-Free Graphs

Result code in IS VaVaI

<a href="https://www.isvavai.cz/riv?ss=detail&h=RIV%2F00216208%3A11320%2F23%3A10453197" target="_blank" >RIV/00216208:11320/23:10453197 - isvavai.cz</a>

Result on the web

<a href="https://verso.is.cuni.cz/pub/verso.fpl?fname=obd_publikace_handle&handle=6sy13jYU7t" target="_blank" >https://verso.is.cuni.cz/pub/verso.fpl?fname=obd_publikace_handle&handle=6sy13jYU7t</a>

DOI - Digital Object Identifier

<a href="http://dx.doi.org/10.1007/s00453-022-01052-5" target="_blank" >10.1007/s00453-022-01052-5</a>

Result language

angličtina

Original language name

Parameterized Inapproximability of Independent Set in H-Free Graphs

Original language description

We study the Independent Set problem in H-free graphs, i.e., graphs excluding some fixed graph H as an induced subgraph. We prove several inapproximability results both for polynomial-time and parameterized algorithms. Halldórsson [SODA 1995] showed that for every δ&gt; 0 the Independent Set problem has a polynomial-time (d-12+δ)-approximation algorithm in K1,d-free graphs. We extend this result by showing that Ka,b-free graphs admit a polynomial-timeO(α(G) 1-1/a) -approximation, where α(G) is the size of a maximum independent set in G. Furthermore, we complement the result of Halldórsson by showing that for some γ= Θ (d/ log d) , there is no polynomial-time γ-approximation algorithm for these graphs, unless NP = ZPP. Bonnet et al. [Algorithmica 2020] showed that Independent Set parameterized by the size k of the independent set is W[1]-hard on graphs which do not contain (1) a cycle of constant length at least 4, (2) the star K1 , 4, and (3) any tree with two vertices of degree at least 3 at constant distance. We strengthen this result by proving three inapproximability results under different complexity assumptions for almost the same class of graphs (we weaken conditions (1) and (2) that G does not contain a cycle of constant length at least 5 or K1 , 5). First, under the ETH, there is no f(k) . no(k/logk) algorithm for any computable function f. Then, under the deterministic Gap-ETH, there is a constant δ&gt; 0 such that no δ-approximation can be computed in f(k) . nO(1) time. Also, under the stronger randomized Gap-ETH there is no such approximation algorithm with runtime f(k).no(k). Finally, we consider the parameterization by the excluded graph H, and show that under the ETH, Independent Set has no no(α(H)) algorithm in H-free graphs. Also, we prove that there is no d/ ko(1)-approximation algorithm for K1,d-free graphs with runtime f(d, k) . nO(1), under the deterministic Gap-ETH.

Czech name

—

Czech description

—

Type

J_imp - 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

<a href="/en/project/GX19-27871X" target="_blank" >GX19-27871X: Efficient approximation algorithms and circuit complexity</a><br>

Continuities

P - Projekt vyzkumu a vyvoje financovany z verejnych zdroju (s odkazem do CEP)

Publication year

2023

Confidentiality

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

Name of the periodical

Algorithmica

ISSN

0178-4617

e-ISSN

1432-0541

Volume of the periodical

85

Issue of the periodical within the volume

October 2022

Country of publishing house

US - UNITED STATES

Number of pages

27

Pages from-to

902-928

UT code for WoS article

000870595900002

EID of the result in the Scopus database

2-s2.0-85140315398