Parameterized Algorithms for Fundamental Network Problems Related to Connectivity
Project goals
Parameterized algorithmics became in the last two decades a standard tool to solve computationally hard (NP-hard) problems. The running time here is expressed in terms of a secondary measure (the parameter) additionally to the input size, which provides a more refined analysis of where the hardness of the problem comes from. Parameterized complexity provides a mathematical framework to analyze these algorithms and also to show that for some problems and parameters there is (probably) no such algorithm. In this research proposal we plan to study several open questions related to fundamental problems in the field of network design within the framework of parameterized complexity. More precisely, we will focus on the following two areas: Steiner-type problems in graphs; Network Measurement, Navigation, and Resource Placement. We plan to provide a systematic multivariate complexity analysis, which we feel is missing in the area.
Keywords
computational intractabilityproblem kernelpolynomial-time preprocessinggraph algorithmnetwork designW[1]-hardnessW[2]-hardnessfixed-parameter tractabilityconnectivitySteiner-type problems
Public support
Provider
Czech Science Foundation
Programme
Post-graduate (doctorate) grants
Call for proposals
Postdoktorandské granty 15 (SGA0201400003)
Main participants
České vysoké učení technické v Praze / Fakulta informačních technologií
Contest type
VS - Public tender
Contract ID
14-13017P
Alternative language
Project name in Czech
Parametrizované algoritmy pro základní síťové problémy spojené se souvislostí
Annotation in Czech
Parametrizované algoritmy se staly v posledních dvou dekádách standardním nástrojem pro řešení výpočetně těžkých (NP-těžkých) problémů. Časová složitost se v tomto vyjadřuje pomocí druhotné míry (parametru) navíc k velikosti vstupu, čímž se dosahuje jemnější analýza původu těžkosti problému. Parametrizovaná složitost představuje matematický rámec pro analyzování takových algoritmů a také umožnuje ukázat, že pro některé problémy a parametry (pravděpodobně) žádný takový algoritmus neexistuje. V rámci toho projektu plánujeme studovat některé otevřené otázky související se základními problémy v oblasti návrhu sítí z pohledu parametrizované složitosti. Přesněji se zaměříme na tyto dvě oblasti: problémy Steinerovského typu v grafech a měření, navigace a umístění zdrojů v sítích. Plánujeme připravit systematickou multivarietní analýzu, která podle našeho názoru v této oblasti chybí.
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 contributed to understanding of algorithms and complexity on network connectivity, multi-cuts, Steiner type problems. The results are very good, and are adequate.
Solution timeline
Realization period - beginning
Jan 1, 2014
Realization period - end
Dec 31, 2016
Project status
U - Finished project
Latest support payment
Apr 5, 2016
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
CEP17-GA0-GP-U/01:1
Data delivery date
Jun 30, 2017
Finance
Total approved costs
1,649 thou. CZK
Public financial support
1,649 thou. CZK
Other public sources
0 thou. CZK
Non public and foreign sources
0 thou. CZK
Recognised costs
1 649 CZK thou.
Public support
1 649 CZK thou.
0%
Provider
Czech Science Foundation
CEP
IN - Informatics
Solution period
01. 01. 2014 - 31. 12. 2016