All

What are you looking for?

All
Projects
Results
Organizations

Quick search

  • Projects supported by TA ČR
  • Excellent projects
  • Projects with the highest public support
  • Current projects

Smart search

  • That is how I find a specific +word
  • That is how I leave the -word out of the results
  • “That is how I can find the whole phrase”

Computational Complexity of Covering Multigraphs with Semi-Edges: Small Cases

The result's identifiers

  • Result code in IS VaVaI

    <a href="https://www.isvavai.cz/riv?ss=detail&h=RIV%2F00216224%3A14330%2F21%3A00119288" target="_blank" >RIV/00216224:14330/21:00119288 - isvavai.cz</a>

  • Alternative codes found

    RIV/00216208:11320/21:10436970

  • Result on the web

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

  • DOI - Digital Object Identifier

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

Alternative languages

  • Result language

    angličtina

  • Original language name

    Computational Complexity of Covering Multigraphs with Semi-Edges: Small Cases

  • Original language description

    We initiate the study of computational complexity of graph coverings, aka locally bijective graph homomorphisms, for graphs with semi-edges. The notion of graph covering is a discretization of coverings between surfaces or topological spaces, a notion well known and deeply studied in classical topology. Graph covers have found applications in discrete mathematics for constructing highly symmetric graphs, and in computer science in the theory of local computations. In 1991, Abello et al. asked for a classification of the computational complexity of deciding if an input graph covers a fixed target graph, in the ordinary setting (of graphs with only edges). Although many general results are known, the full classification is still open. In spite of that, we propose to study the more general case of covering graphs composed of normal edges (including multiedges and loops) and so-called semi-edges. Semi-edges are becoming increasingly popular in modern topological graph theory, as well as in mathematical physics. They also naturally occur in the local computation setting, since they are lifted to matchings in the covering graph. We show that the presence of semi-edges makes the covering problem considerably harder; e.g., it is no longer sufficient to specify the vertex mapping induced by the covering, but one necessarily has to deal with the edge mapping as well. We show some solvable cases and, in particular, completely characterize the complexity of the already very nontrivial problem of covering one- and two-vertex (multi)graphs with semi-edges. Our NP-hardness results are proven for simple input graphs, and in the case of regular two-vertex target graphs, even for bipartite ones. We remark that our new characterization results also strengthen previously known results for covering graphs without semi-edges, and they in turn apply to an infinite class of simple target graphs with at most two vertices of degree more than two. Some of the results are moreover proven in a more general setting (e.g., finding k-tuples of pairwise disjoint perfect matchings in regular graphs, or finding equitable partitions of regular bipartite graphs).

  • Czech name

  • Czech description

Classification

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

Result continuities

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

Others

  • Publication year

    2021

  • Confidentiality

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

Data specific for result type

  • Article name in the collection

    46th International Symposium on Mathematical Foundations of Computer Science (MFCS 2021)

  • ISBN

    9783959772013

  • ISSN

    1868-8969

  • e-ISSN

  • Number of pages

    15

  • Pages from-to

    „21:1“-„21:15“

  • Publisher name

    Schloss Dagstuhl -- Leibniz-Zentrum f{"u}r Informatik

  • Place of publication

    Dagstuhl

  • Event location

    Tallin

  • Event date

    Aug 23, 2021

  • Type of event by nationality

    WRD - Celosvětová akce

  • UT code for WoS article