English (United Kingdom)

https://curated-unify.zendy.io/wp-json/zendy-region/v1/featured_content/oa?rat=en

https://curated-unify.zendy.io/wp-json/zendy-region/v1/highlighted_journal/

Global: Zendy Tools annual

Presents the keyphrase highlighting as premium feature

Keyphrase Highlighting

Presents the summarisation as premium feature

Summarisation

Insights

Presents the pdf analysis as premium feature

PDF Analysis

Presents the zaia usage as premium feature

ZAIA

Global: Zendy Tools monthly

Global: Zendy Plus monthly

Presents the access of premium content as premium feature

Premium Content

Global: Zendy Plus annual

Global: Zendy Free Plan

We initiate the study of computational complexity of graph coverings, akalocally bijective graph homomorphisms, for {\em graphs with semi-edges}. Thenotion of graph covering is a discretization of coverings between surfaces ortopological spaces, a notion well known and deeply studied in classicaltopology. Graph covers have found applications in discrete mathematics forconstructing highly symmetric graphs, and in computer science in the theory oflocal computations. In 1991, Abello et al. asked for a classification of thecomputational complexity of deciding if an input graph covers a fixed targetgraph, in the ordinary setting (of graphs with only edges). Although manygeneral results are known, the full classification is still open. In spite ofthat, we propose to study the more general case of covering graphs composed ofnormal edges (including multiedges and loops) and so-called semi-edges.Semi-edges are becoming increasingly popular in modern topological graphtheory, as well as in mathematical physics. They also naturally occur in thelocal computation setting, since they are lifted to matchings in the coveringgraph. We show that the presence of semi-edges makes the covering problemconsiderably harder; e.g., it is no longer sufficient to specify the vertexmapping induced by the covering, but one necessarily has to deal with the edgemapping as well. We show some solvable cases, and completely characterize thecomplexity of the already very nontrivial problem of covering one- andtwo-vertex (multi)graphs with semi-edges. Our NP-hardness results are provenfor simple input graphs, and in the case of regular two-vertex target graphs,even for bipartite ones. This provides a strengthening of previously knownresults for covering graphs without semi-edges, and may contribute to betterunderstanding of this notion and its complexity.

Computational Complexity of Covering Two-vertex Multigraphs with Semi-edges