Graph Covers: Where Topology Meets Computer Science, and Simple Means Difficult

Kód výsledku v 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>

Výsledek na webu

<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>

Jazyk výsledku

angličtina

Název v původním jazyce

Graph Covers: Where Topology Meets Computer Science, and Simple Means Difficult

Popis výsledku v původním jazyce

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.

Název v anglickém jazyce

Graph Covers: Where Topology Meets Computer Science, and Simple Means Difficult

Popis výsledku anglicky

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.

Druh

D - Stať ve sborníku

CEP obor

—

OECD FORD obor

10201 - Computer sciences, information science, bioinformathics (hardware development to be 2.2, social aspect to be 5.8)

Projekt

<a href="/cs/project/GA20-15576S" target="_blank" >GA20-15576S: Nakrývání grafů: Symetrie a složitost</a><br>

Návaznosti

P - Projekt vyzkumu a vyvoje financovany z verejnych zdroju (s odkazem do CEP)

Rok uplatnění

2023

Kód důvěrnosti údajů

S - Úplné a pravdivé údaje o projektu nepodléhají ochraně podle zvláštních právních předpisů

Název statě ve sborníku

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

—

Počet stran výsledku

9

Strana od-do

3-11

Název nakladatele

Springer

Místo vydání

Cham

Místo konání akce

Hsinchu

Datum konání akce

22. 3. 2023

Typ akce podle státní příslušnosti

WRD - Celosvětová akce

Kód UT WoS článku

—