FPT Inapproximability of Directed Cut and Connectivity Problems

Result code in 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>
Result on the web
<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>

Result language
angličtina
Original language name
FPT Inapproximability of Directed Cut and Connectivity Problems
Original language description
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 "gap-instances" under stronger hypotheses such as the (Gap-)Exponential Time Hypothesis (ETH).
Czech name
—
Czech description
—

Type
D - Article in proceedings
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
2019
Confidentiality
S - Úplné a pravdivé údaje o projektu nepodléhají ochraně podle zvláštních právních předpisů

Article name in the collection
14th International Symposium on Parameterized and Exact Computation (IPEC 2019)
ISBN
978-3-95977-129-0
ISSN
1868-8969
e-ISSN
—
Number of pages
20
Pages from-to
20
Publisher name
Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik
Place of publication
Dagstuhl
Event location
Munich, Germany
Event date
Sep 11, 2019
Type of event by nationality
WRD - Celosvětová akce
UT code for WoS article
—

Similar results(10)