Computational Complexity of Covering Disconnected Multigraphs

Result code in 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>

Result on the web

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

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

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

Result was created during the realization of more than one project. More information in the Projects tab.

Continuities

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

Publication year

2021

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

FUNDAMENTALS OF COMPUTATION THEORY, FCT 2021

ISBN

978-3-030-86593-1

ISSN

0302-9743

e-ISSN

1611-3349

Number of pages

15

Pages from-to

85-99

Publisher name

SPRINGER INTERNATIONAL PUBLISHING AG

Place of publication

CHAM

Event location

Natl Tech Univ Athens

Event date

Sep 12, 2021

Type of event by nationality

WRD - Celosvětová akce

UT code for WoS article

000722594000006