FPT Inapproximability of Directed Cut and Connectivity Problems

Kód výsledku v IS VaVaI

<a href="https://www.isvavai.cz/riv?ss=detail&h=RIV%2F00216208%3A11320%2F19%3A10404753" target="_blank" >RIV/00216208:11320/19:10404753 - isvavai.cz</a>

Výsledek na webu

<a href="https://doi.org/10.4230/LIPIcs.IPEC.2019.8" target="_blank" >https://doi.org/10.4230/LIPIcs.IPEC.2019.8</a>

DOI - Digital Object Identifier

<a href="http://dx.doi.org/10.4230/LIPIcs.IPEC.2019.8" target="_blank" >10.4230/LIPIcs.IPEC.2019.8</a>

Jazyk výsledku

angličtina

Název v původním jazyce

FPT Inapproximability of Directed Cut and Connectivity Problems

Popis výsledku v původním jazyce

Cut problems and connectivity problems on digraphs are two well-studied classes of problems from the viewpoint of parameterized complexity. After a series of papers over the last decade, we now have (almost) tight bounds for the running time of several standard variants of these problems parameterized by two parameters: the number k of terminals and the size p of the solution. When there is evidence of FPT intractability, then the next natural alternative is to consider FPT approximations. In this paper, we show two types of results for directed cut and connectivity problems, building on existing results from the literature: first is to circumvent the hardness results for these problems by designing FPT approximation algorithms, or alternatively strengthen the existing hardness results by creating &quot;gap-instances&quot; under stronger hypotheses such as the (Gap-)Exponential Time Hypothesis (ETH).

Název v anglickém jazyce

FPT Inapproximability of Directed Cut and Connectivity Problems

Popis výsledku anglicky

Cut problems and connectivity problems on digraphs are two well-studied classes of problems from the viewpoint of parameterized complexity. After a series of papers over the last decade, we now have (almost) tight bounds for the running time of several standard variants of these problems parameterized by two parameters: the number k of terminals and the size p of the solution. When there is evidence of FPT intractability, then the next natural alternative is to consider FPT approximations. In this paper, we show two types of results for directed cut and connectivity problems, building on existing results from the literature: first is to circumvent the hardness results for these problems by designing FPT approximation algorithms, or alternatively strengthen the existing hardness results by creating &quot;gap-instances&quot; under stronger hypotheses such as the (Gap-)Exponential Time Hypothesis (ETH).

Druh

D - Stať ve sborníku

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í

2019

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 statě ve sborníku

14th International Symposium on Parameterized and Exact Computation (IPEC 2019)

ISBN

978-3-95977-129-0

ISSN

1868-8969

e-ISSN

—

Počet stran výsledku

20

Strana od-do

20

Název nakladatele

Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik

Místo vydání

Dagstuhl

Místo konání akce

Munich, Germany

Datum konání akce

11. 9. 2019

Typ akce podle státní příslušnosti

WRD - Celosvětová akce

Kód UT WoS článku

—