Parameterized Inapproximability of Independent Set in H-Free Graphs

Kód výsledku v 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>

Výsledek na webu

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

Jazyk výsledku

angličtina

Název v původním jazyce

Parameterized Inapproximability of Independent Set in H-Free Graphs

Popis výsledku v původním jazyce

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.

Název v anglickém jazyce

Parameterized Inapproximability of Independent Set in H-Free Graphs

Popis výsledku anglicky

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.

Druh

J_imp - Článek v periodiku v databázi Web of Science

CEP obor

—

OECD FORD obor

10201 - Computer sciences, information science, bioinformathics (hardware development to be 2.2, social aspect to be 5.8)

Projekt

<a href="/cs/project/GX19-27871X" target="_blank" >GX19-27871X: Efektivní aproximační algoritmy a obvodová složitost</a><br>

Návaznosti

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

Rok uplatnění

2023

Kód důvěrnosti údajů

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

Název periodika

Algorithmica

ISSN

0178-4617

e-ISSN

1432-0541

Svazek periodika

85

Číslo periodika v rámci svazku

October 2022

Stát vydavatele periodika

US - Spojené státy americké

Počet stran výsledku

27

Strana od-do

902-928

Kód UT WoS článku

000870595900002

EID výsledku v databázi Scopus

2-s2.0-85140315398