Computational complexity of covering disconnected multigraphs

Kód výsledku v 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>

Výsledek na webu

<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>

Jazyk výsledku

angličtina

Název v původním jazyce

Computational complexity of covering disconnected multigraphs

Popis výsledku v původním jazyce

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.

Název v anglickém jazyce

Computational complexity of covering disconnected multigraphs

Popis výsledku anglicky

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.

Druh

J_imp - Článek v periodiku v databázi Web of Science

CEP obor

—

OECD FORD obor

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

Projekt

<a href="/cs/project/GA20-15576S" target="_blank" >GA20-15576S: Nakrývání grafů: Symetrie a složitost</a><br>

Návaznosti

P - Projekt vyzkumu a vyvoje financovany z verejnych zdroju (s odkazem do CEP)

Rok uplatnění

2024

Kód důvěrnosti údajů

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

Název periodika

Discrete Applied Mathematics

ISSN

0166-218X

e-ISSN

1872-6771

Svazek periodika

Neuveden

Číslo periodika v rámci svazku

359

Stát vydavatele periodika

NL - Nizozemsko

Počet stran výsledku

15

Strana od-do

229-243

Kód UT WoS článku

001295715300001

EID výsledku v databázi Scopus

2-s2.0-85200987609