Structural properties, parameterized tractability and hardness in combinatorial problems
Project goals
The concept of parameterized tractability allows for guaranteed efficient solutions of some instances - as determined by the parameter, of problems which are intractable in their full generality. Our proposal addresses various questions belonging to theoretical foundations of parameterized algorithmics, namely those related to structural and topological graph theory, and to logic and interpretations in graphs. Among the problems we propose to investigate are algorithmic metatheorems for FO properties on dense graph classes, FO interpretations in sparse classes and their structural characterizations, parameterized tractability of graph crossing number and planar insertion problems, structural characterization of crossing-critical graphs, and other.
Keywords
structural graph theoryparameterized algorithmicslogicalgorithmic metatheoremsgeometric graphs
Public support
Provider
Czech Science Foundation
Programme
Standard projects
Call for proposals
Standardní projekty 21 (SGA0201700001)
Main participants
Masarykova univerzita / Fakulta informatiky
Contest type
VS - Public tender
Contract ID
17-00837S
Alternative language
Project name in Czech
Strukturální vlastnosti, parametrizovaná řešitelnost a těžkost v kombinatorických problémech
Annotation in Czech
Pojetí parametrizované složitosti poskytuje garantovaná efektivní řešení některých instancí (definovaných daným parametrem) u problémů, které jsou v celé své obecnosti efektivně neřešitelné. Náš návrh se týká různých otázek náležejících do teoretických základů parametrizované algoritmiky, především těch vztahujících se ke strukturální a topologické teorie grafů, logice a interpretacím grafů. Mezi problémy, které budeme zkoumat, náleží algoritmické metavěty pro FO vlastnosti na hustých třídách grafů, FO interpretace v řídkých třídách a jejich strukturální charakterizace, parametrizovaná řešitelnost problémů průsečíkového čísla grafu a rovinného vkládání, strukturální popis průsečíkově-kritických grafů a další.
Scientific branches
R&D category
ZV - Basic research
CEP classification - main branch
IN - Informatics
CEP - secondary branch
BA - General mathematics
CEP - another secondary branch
—
10101 - Pure mathematics
10201 - Computer sciences, information science, bioinformathics (hardware development to be 2.2, social aspect to be 5.8)
Completed project evaluation
Provider evaluation
U - Uspěl podle zadání (s publikovanými či patentovanými výsledky atd.)
Project results evaluation
Project resulted into new research results in parametrized complexity theory, structural graph theory, properties of topological and geometric graphs, namely crossing numbers. Results are published in leading journals and rank A or B conferences. The final card sufficiently characterizes the project results. Agency rules were obeyed.
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
4,758 thou. CZK
Public financial support
3,294 thou. CZK
Other public sources
1,440 thou. CZK
Non public and foreign sources
0 thou. CZK
Basic information
Recognised costs
4 758 CZK thou.
Public support
3 294 CZK thou.
69%
Provider
Czech Science Foundation
CEP
IN - Informatics
Solution period
01. 01. 2017 - 31. 12. 2019