Computational Complexity of Covering Regular Trees

Result code in IS VaVaI

<a href="https://www.isvavai.cz/riv?ss=detail&h=RIV%2F00216208%3A11320%2F25%3A10509954" target="_blank" >RIV/00216208:11320/25:10509954 - isvavai.cz</a>

Result on the web

<a href="https://doi.org/10.4230/LIPIcs.MFCS.2025.26" target="_blank" >https://doi.org/10.4230/LIPIcs.MFCS.2025.26</a>

DOI - Digital Object Identifier

<a href="http://dx.doi.org/10.4230/LIPIcs.MFCS.2025.26" target="_blank" >10.4230/LIPIcs.MFCS.2025.26</a>

Result language

angličtina

Original language name

Computational Complexity of Covering Regular Trees

Original language description

A graph covering projection, also referred to as a locally bijective homomorphism, is a mapping between the vertices and edges of two graphs that preserves incidences and is a local bijection. This concept originates in topological graph theory but has also found applications in combinatorics and theoretical computer science. In this paper we consider undirected graphs in the most general setting - graphs may contain multiple edges, loops, and semi-edges. This is in line with recent trends in topological graph theory and mathematical physics. We advance the study of the computational complexity of the H-Cover problem, which asks whether an input graph allows a covering projection onto a parameter graph H. The quest for a complete characterization started in 1990&apos;s. Several results for simple graphs or graphs without semi-edges have been known, the role of semi-edges in the complexity setting has started to be investigated only recently. One of the most general known NP-hardness results states that HCover is NP-complete for every simple connected regular graph of valency greater than two. We complement this result by considering regular graphs H arising from connected acyclic graphs by adding semi-edges. Namely, we prove that any graph obtained by adding semi-edges to the vertices of a tree making it a d-regular graph with d &gt;= 3, defines an NP-complete graph covering problem. In line with the so called Strong Dichotomy Conjecture, we prove that the NP-hardness holds even for simple graphs on input.

Czech name

—

Czech description

—

Type

D - Article in proceedings

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

2025

Confidentiality

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

Article name in the collection

Leibniz International Proceedings in Informatics Lipics

ISBN

978-3-95977-388-1

ISSN

—

e-ISSN

—

Number of pages

19

Pages from-to

26.1-26.19

Publisher name

Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing

Place of publication

Dagstuhl

Event location

Warsaw

Event date

Aug 25, 2025

Type of event by nationality

WRD - Celosvětová akce

UT code for WoS article

—