Structure of tractable instances of hard algorithmic problems on graphs
Project goals
One of the fundamental questions in theoretical CS is how to approach problems which are intractable in their full generality. Our proposal is to investigate the internal structure of tractable instances of such generally hard problems on graphs, namely those dealing with structural and topological graph theory, geometric graphs, and of problems definable in various logics. In particular, we propose to investigate algorithmic and complexity theoretical aspects of new width and sparsity parameters of graph classes, properties of geometric representations of graphs, tractable instances for the FO model checking problem, and the detailed structure of the graph crossing number problem.
Keywords
graph theoryalgorithmic complexitywidth parametersmodel checkinggeometric graphcrossing number
Public support
Provider
Czech Science Foundation
Programme
Standard projects
Call for proposals
SGA0202000001
Main participants
Masarykova univerzita / Fakulta informatiky
Contest type
VS - Public tender
Contract ID
20-04567S
Alternative language
Project name in Czech
Struktura efektivně řešitelných případů těžkých algoritmických problémů na grafech
Annotation in Czech
Jednou ze základních otázek teoretické informatiky je jak řešit algoritmické problémy, které jsou v plné obecnosti efektivně neřešitelné. Naším návrhem je zkoumat vnitřní strukturu efektivně řešitelných případů takových obecně těžkých problémů na grafech, především otázky z oblastí strukturální a topologické teorie grafů, geometrických grafů a ty týkající se problémů definovaných v různých logikách. Konkrétně navrhujeme studovat algoritmické a složitostní stránky nových šířkových a "řídkostních" parametrů tříd grafů, vlastnosti geometrických reprezentací grafů, efektivně řešitelné případy rozhodování FO vlastností a podrobnou strukturu problému průsečíkového čísla grafu.
Scientific branches
R&D category
ZV - Basic research
OECD FORD - main branch
10201 - Computer sciences, information science, bioinformathics (hardware development to be 2.2, social aspect to be 5.8)
OECD FORD - secondary branch
—
OECD FORD - another secondary branch
—
AF - Documentation, librarianship, work with information
BC - Theory and management systems
BD - Information theory
IN - Informatics
Completed project evaluation
Provider evaluation
V - Vynikající výsledky projektu (s mezinárodním významem atd.)
Project results evaluation
The project resulted in a number of very good and a large volume of good publications, thus the outcome is very good. The project successfully involved a number of junior researchers.
Solution timeline
Realization period - beginning
Jan 1, 2020
Realization period - end
Dec 31, 2022
Project status
U - Finished project
Latest support payment
May 11, 2022
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
CEP23-GA0-GA-U
Data delivery date
Jun 26, 2023
Finance
Total approved costs
8,174 thou. CZK
Public financial support
6,521 thou. CZK
Other public sources
1,653 thou. CZK
Non public and foreign sources
0 thou. CZK
Basic information
Recognised costs
8 174 CZK thou.
Public support
6 521 CZK thou.
79%
Provider
Czech Science Foundation
OECD FORD
Computer sciences, information science, bioinformathics (hardware development to be 2.2, social aspect to be 5.8)
Solution period
01. 01. 2020 - 31. 12. 2022