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%2F21%3A10436901" target="_blank" >RIV/00216208:11320/21:10436901 - isvavai.cz</a>

Výsledek na webu

<a href="https://doi.org/10.1007/978-3-030-86593-1_6" target="_blank" >https://doi.org/10.1007/978-3-030-86593-1_6</a>

DOI - Digital Object Identifier

<a href="http://dx.doi.org/10.1007/978-3-030-86593-1_6" target="_blank" >10.1007/978-3-030-86593-1_6</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 nonequivalent definitions of 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. Despite of this, we argue that the third variant, equitable covers, is the right one, when considering covers of colored (multi)graphs. Moreover, the complexity of surjective and equitable covers differ from the fixed parameter complexity point of view. We conclude the paper by a complete characterization of the complexity of covering 2-vertex colored multigraphs with semi-edges. We present the results in the utmost generality and strength. In accord with the current trends we consider (multi)graphs with semi-edges, and, on the other hand, we aim at proving the NP-completeness results for 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 nonequivalent definitions of 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. Despite of this, we argue that the third variant, equitable covers, is the right one, when considering covers of colored (multi)graphs. Moreover, the complexity of surjective and equitable covers differ from the fixed parameter complexity point of view. We conclude the paper by a complete characterization of the complexity of covering 2-vertex colored multigraphs with semi-edges. We present the results in the utmost generality and strength. In accord with the current trends we consider (multi)graphs with semi-edges, and, on the other hand, we aim at proving the NP-completeness results for simple input graphs.

Druh

D - Stať ve sborníku

CEP obor

—

OECD FORD obor

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

Projekt

Výsledek vznikl pri realizaci vícero projektů. Více informací v záložce Projekty.

Návaznosti

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

Rok uplatnění

2021

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 statě ve sborníku

FUNDAMENTALS OF COMPUTATION THEORY, FCT 2021

ISBN

978-3-030-86593-1

ISSN

0302-9743

e-ISSN

1611-3349

Počet stran výsledku

15

Strana od-do

85-99

Název nakladatele

SPRINGER INTERNATIONAL PUBLISHING AG

Místo vydání

CHAM

Místo konání akce

Natl Tech Univ Athens

Datum konání akce

12. 9. 2021

Typ akce podle státní příslušnosti

WRD - Celosvětová akce

Kód UT WoS článku

000722594000006