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