List Covering of Regular Multigraphs with Semi-edges

Result code in IS VaVaI

<a href="https://www.isvavai.cz/riv?ss=detail&h=RIV%2F00216208%3A11320%2F24%3A10489534" target="_blank" >RIV/00216208:11320/24:10489534 - isvavai.cz</a>

Result on the web

<a href="https://verso.is.cuni.cz/pub/verso.fpl?fname=obd_publikace_handle&handle=kbKCJQP0Kv" target="_blank" >https://verso.is.cuni.cz/pub/verso.fpl?fname=obd_publikace_handle&handle=kbKCJQP0Kv</a>

DOI - Digital Object Identifier

<a href="http://dx.doi.org/10.1007/s00453-023-01163-7" target="_blank" >10.1007/s00453-023-01163-7</a>

Result language

angličtina

Original language name

List Covering of Regular Multigraphs with Semi-edges

Original language description

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.

Czech name

—

Czech description

—

Type

J_imp - Article in a specialist periodical, which is included in the Web of Science database

CEP classification

—

OECD FORD branch

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

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)

Publication year

2024

Confidentiality

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

Name of the periodical

Algorithmica

ISSN

0178-4617

e-ISSN

1432-0541

Volume of the periodical

86

Issue of the periodical within the volume

3

Country of publishing house

US - UNITED STATES

Number of pages

26

Pages from-to

782-807

UT code for WoS article

001118644500001

EID of the result in the Scopus database

2-s2.0-85168939540