Computational complexity of covering disconnected multigraphs

Result code in IS VaVaI

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

Result on the web

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

DOI - Digital Object Identifier

<a href="http://dx.doi.org/10.1016/j.dam.2024.07.035" target="_blank" >10.1016/j.dam.2024.07.035</a>

Result language

angličtina

Original language name

Computational complexity of covering disconnected multigraphs

Original language description

The notion of graph covers is a discretization of covering spaces introduced and deeply studied in topology. In discrete mathematics and theoretical computer science, they have attained a lot of attention from both the structural and complexity perspectives. Nonetheless, disconnected graphs were usually omitted from the considerations with the explanation that it is sufficient to understand coverings of the connected components of the target graph by components of the source one. However, different (but equivalent) versions of the definition of covers of connected graphs generalize to non-equivalent definitions for disconnected graphs. The aim of this paper is to summarize this issue and to compare three different approaches to covers of disconnected graphs: (1) locally bijective homomorphisms, (2) globally surjective locally bijective homomorphisms (which we call surjective covers), and (3) locally bijective homomorphisms which cover every vertex the same number of times (which we call equitable covers). The standpoint of our comparison is the complexity of deciding if an input graph covers a fixed target graph. We show that both surjective and equitable covers satisfy what certainly is a natural and welcome property: covering a disconnected graph is polynomial-time decidable if such it is for every connected component of the graph, and it is NP-complete if it is NP-complete for at least one of its components. We further argue that the third variant, equitable covers, is the most natural one, namely when considering covers of colored graphs. Moreover, the complexity of surjective and equitable covers differ from the fixed parameter complexity point of view. In line with the current trends in topological graph theory, as well as its applications in mathematical physics, we consider graphs in a very general sense: our graphs may contain loops, multiple edges and also semi-edges. Moreover, both vertices and edges may be colored, in which case the covering projection must respect the colors. We conclude the paper by a complete characterization of the complexity of covering 2-vertex colored graphs, and show that poly-time/NP-completeness dichotomy holds true for this case. We actually aim for a stronger dichotomy. All our polynomial-time algorithms work for arbitrary input graphs, while the NP-completeness theorems hold true even in the case of simple input 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

Discrete Applied Mathematics

ISSN

0166-218X

e-ISSN

1872-6771

Volume of the periodical

Neuveden

Issue of the periodical within the volume

359

Country of publishing house

NL - THE KINGDOM OF THE NETHERLANDS

Number of pages

15

Pages from-to

229-243

UT code for WoS article

001295715300001

EID of the result in the Scopus database

2-s2.0-85200987609