Sie befinden Sich nicht im Netzwerk der Universität Paderborn. Der Zugriff auf elektronische Ressourcen ist gegebenenfalls nur via VPN oder Shibboleth (DFN-AAI) möglich. mehr Informationen...
List Covering of Regular Multigraphs with Semi-edges
Ist Teil von
Algorithmica, 2024-03, Vol.86 (3), p.782-807
Ort / Verlag
New York: Springer US
Erscheinungsjahr
2024
Quelle
Alma/SFX Local Collection
Beschreibungen/Notizen
In line with the recent development in topological graph theory, we are considering undirected graphs that are allowed to contain
multiple edges
,
loops
, and
semi-edges
. A graph is called
simple
if it contains no semi-edges, no loops, and no multiple edges. A graph covering projection, also known as a locally bijective homomorphism, is a mapping between vertices and edges of two graphs which preserves incidences and which is a local bijection on the edge-neighborhood of every vertex. This notion stems from topological graph theory, but has also found applications in combinatorics and theoretical computer science. It has been known that for every fixed simple regular graph
H
of valency greater than 2, deciding if an input graph covers
H
is NP-complete. Graphs with semi-edges have been considered in this context only recently and only partial results on the complexity of covering such graphs are known so far. In this paper we consider the list version of the problem, called
List
-
H
-
Cover
, where the vertices and edges of the input graph come with lists of admissible targets. Our main result reads that the
List
-
H
-
Cover
problem is NP-complete for every regular graph
H
of valency greater than 2 which contains at least one semi-simple vertex (i.e., a vertex which is incident with no loops, with no multiple edges and with at most one semi-edge). Using this result we show the NP-co/polytime dichotomy for the computational complexity of
List
-
H
-
Cover
for cubic graphs.