Tight Parameterized Results for Directed Connectivity Problems
Project goals
A parameterized or multivariate analysis became in the last two decades a standard approach for (NP-) hard computational problems. Here, in contrast to classical complexity, the efficiency of algorithms is not measured only with respect to the length of the input instance, but also with respect to a specified parameter. Recently, more focus is put on achieving the best possible polynomial degree as well as the best asymptotic time dependency on the parameter. This is justified by providing matching lower bounds, showing that the existence of significantly faster algorithms is improbable, typically relying on the Exponential Time Hypothesis or its strong form. In this research proposal we target on several fundamental problems in network design related to connectivity in directed graphs from the parameterized perspective. Our aim is to either obtain new algorithms for the problems with better running time than that of the existing algorithms, or to obtain lower bounds showing that such an improvement is unlikely. Our main focus are Steiner-type problems in directed graphs.
Keywords
computational complexitygraph algorithmsparameterized complexitySteiner treeNetwork design problemskernelization
Public support
Provider
Czech Science Foundation
Programme
Standard projects
Call for proposals
Standardní projekty 21 (SGA0201700001)
Main participants
České vysoké učení technické v Praze / Fakulta informačních technologií
Contest type
VS - Public tender
Contract ID
17-20065S
Alternative language
Project name in Czech
Těsné parametrizované výsledky pro problémy orientované souvislosti
Annotation in Czech
Parametrizovaná nebo multivarietní analýza se v minulých dvou dekádách stala standardním přístupem k (NP-) těžkým problémům. Oproti klasické výpočetní složitosti se zde efektivita algoritmů měří nejen vzhledem k délce vstupu, ale také vzhledem k určenému parametru. V poslední době je kladen větší důraz na získání nejlepšího možného stupně polynomu stejně jako nejlepší asymptotické časové závislosti na parametru. To je prokázáno předvedením dolních mezí ukazujících, že existence výrazně rychlejších algoritmů je nepravděpodobná, typicky založených na hypotéze exponenciálního času, nebo její silné formě. V tomto návrhu projektu se zaměřujeme na několik zásadních problémů v návrhu sítí spojených se souvislostí v orientovaných grafech z parametrizovaného pohledu. Náš cíl je buď získat nové algoritmy pro tyto problémy s lepší časovou složitostí než mají existující algoritmy, nebo získat dolní meze ukazující, že takové vylepšení je nepravděpodobné. Naším hlavním zaměřením jsou problémy Steinerovského typu na orientovaných grafech.
Scientific branches
Completed project evaluation
Provider evaluation
U - Uspěl podle zadání (s publikovanými či patentovanými výsledky atd.)
Project results evaluation
The project team achieved a number of results in the area of parameterized complexity. The course of the project was in line with its proposal, and likewise the quantity and the quality of the results obtained. The inclusion of PhD students to the work on the project and substantial international cooperation are commended. The funding was spent following the rules of the Czech Science Foundation.
Solution timeline
Realization period - beginning
Jan 1, 2017
Realization period - end
Dec 31, 2019
Project status
U - Finished project
Latest support payment
Apr 3, 2019
Data delivery to CEP
Confidentiality
S - Úplné a pravdivé údaje o projektu nepodléhají ochraně podle zvláštních právních předpisů
Data delivery code
CEP20-GA0-GA-U/02:1
Data delivery date
Jul 23, 2020
Finance
Total approved costs
1,986 thou. CZK
Public financial support
1,620 thou. CZK
Other public sources
366 thou. CZK
Non public and foreign sources
0 thou. CZK
Basic information
Recognised costs
1 986 CZK thou.
Public support
1 620 CZK thou.
81%
Provider
Czech Science Foundation
CEP
IN - Informatics
Solution period
01. 01. 2017 - 31. 12. 2019