Parameterized algorithms and kernelization in the context of discrete mathematics and logic
Project goals
A possible approach to overcome the notorious intractability of NP-hard problems is provided by the theory of Parameterized Complexity: an auxiliary "parameter" - an arbitrary number k - is assigned to each input, such that a computable function of k upper-bounds the computational complexity of the problem. The general goal here is to choose a parameter k which attains low values on interesting inputs, thus leading to efficient algorithms on inputs characterized by such k. The project will search for suitable structural and geometric parameters for classes of combinatorial objects (graphs) and use the new findings to obtain more efficient parameterized algorithms, as well as, so-called algorithmic metatheorems based on logic description. In particular, it will continue the recent very successful research of parameterized complexity lower bounds. Metatheorems for kernelization (parameterized preprocessing) of problems, and search for usable geometric parameters (e.g., coming from an input representation of the graph) are specifically mentioned among the new research tasks.
Keywords
parameterized complexitykernelizationalgorithmic metatheoremscomplexity lower boundsMSO logicgraphs
Public support
Provider
Czech Science Foundation
Programme
Standard projects
Call for proposals
Standardní projekty 18 (SGA0201400001)
Main participants
Masarykova univerzita / Fakulta informatiky
Contest type
VS - Public tender
Contract ID
14-03501S
Alternative language
Project name in Czech
Parametrizované algoritmy a kernelizace v kontextu diskrétní matematiky a logiky
Annotation in Czech
Jeden z možných přístupů ke zdolání zdánlivě nepřekonatelné překážky NP-těžkosti algoritmických problémů nám podává teorie parametrizované složitosti: Vstup těžkého problému je opatřen doplňkovým parametrem - libovolným číslem k, jehož jakákoliv počitatelná funkce omezuje výpočetní složitost našeho problému. Snahou je volit parametr k tak, aby jeho hodnota byla na zajímavých vstupech nízká, což následně umožňuje efektivní řešení problémů na takto charakterizovaných vstupech. V projektu budou hledány a studovány vhodné strukturální a geometrické parametry pro třídy kombinatorických objektů (grafů) a nové poznatky budou využity v návrhu lepších parametrizovaných algoritmů a obecných logikou popsaných tzv. algoritmických metavět. Mimo jiné bude pokračovat nedávno velmi úspěšné nalézání dolních mezí parametrizované řešitelnosti problémů. Mezi novými směry výzkumu v navržené oblasti jsou především zmíněny oblasti metavět pro kernelizaci (efektivní parametrické předzpracování) problémů a využití geometrických parametrů (vycházejících například z reprezentace vstupního grafu).
Scientific branches
Completed project evaluation
Provider evaluation
V - Vynikající výsledky projektu (s mezinárodním významem atd.)
Project results evaluation
The team (although modest in size: two senior researchers, two doctoral students) significantly contributed by important results to all four topics declared in the project propsal. The results were accepted by international scientific community: three papers presented at A* conferences, 5 papers published in prestigious journals.
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-GA-U/03:1
Data delivery date
Jun 28, 2017
Finance
Total approved costs
4,458 thou. CZK
Public financial support
4,458 thou. CZK
Other public sources
0 thou. CZK
Non public and foreign sources
0 thou. CZK
Basic information
Recognised costs
4 458 CZK thou.
Public support
4 458 CZK thou.
100%
Provider
Czech Science Foundation
CEP
IN - Informatics
Solution period
01. 01. 2014 - 31. 12. 2016