Graph Covers: Symmetries and Complexity
Project goals
The concept of symmetry is as old as mathematics. In modern mathematics, it is formalized by the concept of the automorphism of a considered structure. In the present project we shall restrict ourselves to investigation of one- and two-dimensional structures, namely, to graphs, surfaces, and their quotients, that is to orbifolds of dimension 1 and 2. Coverings between graphs and surfaces were extensively investigated and found many applications. Much less is known about the computational complexity of graph covering problems. The project is aimed at investigation of computational complexity of such problems, including several problems that either generalize the graph isomorphism problem, or ask to solve it for restricted classes of graphs. In this framework we hope to understand better the behavior of the complexity of the problems under investigation with the aim to identify the borderline between P and GI-completeness on one-hand side, and GI-completeness and NP-hardness on the other one.
Keywords
GraphAutomorphismAutomorphism groupGraph coveringComputational complexity
Public support
Provider
Czech Science Foundation
Programme
Standard projects
Call for proposals
SGA0202000001
Main participants
Univerzita Karlova / Matematicko-fyzikální fakulta
Contest type
VS - Public tender
Contract ID
20-15576S
Alternative language
Project name in Czech
Nakrývání grafů: Symetrie a složitost
Annotation in Czech
Koncept symetrie je stejně starý jako matematika sama. V moderní matematice je formalizován jako koncept automorfismu uvažované struktury. V předkládaném projektu budeme studovat jedno- a dvou-dimenzionální struktury, zejména grafy, plochy a jejich kvocienty, tedy orbity dimenze 1 a 2. Nakrytí grafů a ploch byla intenzivně studována a našla mnoho aplikací. Mnohem méně je ale známo o výpočetní složitosti otázek souvisejících s nakrýváním grafů. Projekt se zaměří na studium výpočetní složitosti těchto otázek, včetně problémů zobecňujících problém isomorfismu grafů, případně tento problém řešící pro omezené třídy grafů. Tímto způsobem doufáme dosáhnout lepšího pochopení výpočetní složitosti studovaných problémů s nadějí na upřesnění hranice mezi polynomiálními a GI-úplnými instancemi na jedné straně, a mezi GI-úplnými a NP-úplnými instancemi na straně druhé.
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
U - Uspěl podle zadání (s publikovanými či patentovanými výsledky atd.)
Project results evaluation
The project delivered a large number of good publications, published in respected international conferences and journals. The outcome is satisfactory for the size and potential of the team. On the negative side, the project resulted in very few top-shelf publication (no CORE A* conference paper, one JCTB paper).
Solution timeline
Realization period - beginning
Jan 1, 2020
Realization period - end
Jun 30, 2023
Project status
U - Finished project
Latest support payment
Apr 1, 2023
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
CEP24-GA0-GA-U
Data delivery date
May 21, 2024
Finance
Total approved costs
8,573 thou. CZK
Public financial support
7,581 thou. CZK
Other public sources
992 thou. CZK
Non public and foreign sources
0 thou. CZK
Recognised costs
8 573 CZK thou.
Public support
7 581 CZK thou.
0%
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 - 30. 06. 2023