Graph Covers: Where Topology Meets Computer Science, and Simple Means Difficult
The result's identifiers
Result code in IS VaVaI
<a href="https://www.isvavai.cz/riv?ss=detail&h=RIV%2F00216208%3A11320%2F23%3A10475554" target="_blank" >RIV/00216208:11320/23:10475554 - isvavai.cz</a>
Result on the web
<a href="https://doi.org/10.1007/978-3-031-27051-2_1" target="_blank" >https://doi.org/10.1007/978-3-031-27051-2_1</a>
DOI - Digital Object Identifier
<a href="http://dx.doi.org/10.1007/978-3-031-27051-2_1" target="_blank" >10.1007/978-3-031-27051-2_1</a>
Alternative languages
Result language
angličtina
Original language name
Graph Covers: Where Topology Meets Computer Science, and Simple Means Difficult
Original language description
We survey old and recent results on the computational complexity of graph covers, also known as locally bijective graph homomorphisms. This notion opens doors to interesting connections. The motivation itself comes from the classical notion of covering spaces in general topology, graph covers find computer science applications as a model of local computation, and in combinatorics they are used for constructing large highly symmetric graphs.More than 30 years ago, Abello et al. [1] asked for a complete characterization of the computational complexity of deciding if an input graph covers a fixed one, and until this day only isolated results are known. We look at this question from several different angles of view - covers as locally constrained graph homomorphisms, covers of multigraphs, covers of graphs with semi-edges, or the list variant of the graph covering question. We also mention several open problems, including the Strong Dichotomy Conjecture for graph covers of Bok et al. [6], stating that for every target multigraph H, the H -Cover problem is either polynomial time solvable for arbitrary input graphs, or NP-complete for simple graphs on input. We justify this conjecture for several infinite classes of target (multi)graphs.
Czech name
—
Czech description
—
Classification
Type
D - Article in proceedings
CEP classification
—
OECD FORD branch
10201 - Computer sciences, information science, bioinformathics (hardware development to be 2.2, social aspect to be 5.8)
Result continuities
Project
<a href="/en/project/GA20-15576S" target="_blank" >GA20-15576S: Graph Covers: Symmetries and Complexity</a><br>
Continuities
P - Projekt vyzkumu a vyvoje financovany z verejnych zdroju (s odkazem do CEP)
Others
Publication year
2023
Confidentiality
S - Úplné a pravdivé údaje o projektu nepodléhají ochraně podle zvláštních právních předpisů
Data specific for result type
Article name in the collection
Chun-Cheng Lin, Bertrand M. T. Lin, Giuseppe Liotta: WALCOM: Algorithms and Computation - 17th International Conference and Workshops, WALCOM 2023, Hsinchu, Taiwan, March 22-24, 2023, Proceedings.
ISBN
978-3-031-27050-5
ISSN
0302-9743
e-ISSN
—
Number of pages
9
Pages from-to
3-11
Publisher name
Springer
Place of publication
Cham
Event location
Hsinchu
Event date
Mar 22, 2023
Type of event by nationality
WRD - Celosvětová akce
UT code for WoS article
—