View in EDS

Computational complexity of covering coloured mixed multigraphs with simple degree partitions.

Saved in:
Bibliographic Details
Title: Computational complexity of covering coloured mixed multigraphs with simple degree partitions.
Authors: Bok, Jan1,2 (AUTHOR) jan.bok@matfyz.cuni.cz, Fiala, Jiří1,3 (AUTHOR) fiala@kam.mff.cuni.cz, Jedličková, Nikola1,3 (AUTHOR) jedlickova@kam.mff.cuni.cz, Kratochvíl, Jan1,3 (AUTHOR) honza@kam.mff.cuni.cz, Seifrtová, Michaela1,3 (AUTHOR) michaela.seifrtova@mff.cuni.cz
Source: Discrete Applied Mathematics. May2026, Vol. 385, p194-221. 28p.
Subjects: Computational complexity, Multigraph, NP-hard problems, Graph theory
Abstract: The notion of graph covers (also referred to as locally bijective homomorphisms) plays an important role in topological graph theory and has found its computer science applications in models of local computation. For a fixed target graph H , the H - Cover problem asks if an input graph G allows a graph covering projection onto H. Despite the fact that the quest for characterizing the computational complexity of H - Cover had been started more than 30 years ago, only a handful of general results have been known so far. In this paper, we present a complete characterization of the computational complexity of covering coloured graphs for the case that every equivalence class in the degree partition of the target graph has at most two vertices. We prove this result in a very general form. Following the lines of current development of topological graph theory, we study graphs in the most relaxed sense of the definition. In particular, we consider graphs that are mixed (they may have both directed and undirected edges), may have multiple edges, loops, and semi-edges. We show that a strong P/NP-complete dichotomy holds true in the sense that for each such fixed target graph H , the H - Cover problem is either polynomial-time solvable for arbitrary inputs, or NP-complete even for simple input graphs. [ABSTRACT FROM AUTHOR]
Copyright of Discrete Applied Mathematics is the property of Elsevier B.V. and its content may not be copied or emailed to multiple sites without the copyright holder's express written permission. Additionally, content may not be used with any artificial intelligence tools or machine learning technologies. However, users may print, download, or email articles for individual use. This abstract may be abridged. No warranty is given about the accuracy of the copy. Users should refer to the original published version of the material for the full abstract. (Copyright applies to all Abstracts.)
Database: Engineering Source
FullText Text:
  Availability: 0
Header DbId: egs
DbLabel: Engineering Source
An: 192194646
AccessLevel: 6
PubType: Academic Journal
PubTypeId: academicJournal
PreciseRelevancyScore: 0
IllustrationInfo
Items – Name: Title
  Label: Title
  Group: Ti
  Data: Computational complexity of covering coloured mixed multigraphs with simple degree partitions.
– Name: Author
  Label: Authors
  Group: Au
  Data: <searchLink fieldCode="AR" term="%22Bok%2C+Jan%22">Bok, Jan</searchLink><relatesTo>1,2</relatesTo> (AUTHOR)<i> jan.bok@matfyz.cuni.cz</i><br /><searchLink fieldCode="AR" term="%22Fiala%2C+Jiří%22">Fiala, Jiří</searchLink><relatesTo>1,3</relatesTo> (AUTHOR)<i> fiala@kam.mff.cuni.cz</i><br /><searchLink fieldCode="AR" term="%22Jedličková%2C+Nikola%22">Jedličková, Nikola</searchLink><relatesTo>1,3</relatesTo> (AUTHOR)<i> jedlickova@kam.mff.cuni.cz</i><br /><searchLink fieldCode="AR" term="%22Kratochvíl%2C+Jan%22">Kratochvíl, Jan</searchLink><relatesTo>1,3</relatesTo> (AUTHOR)<i> honza@kam.mff.cuni.cz</i><br /><searchLink fieldCode="AR" term="%22Seifrtová%2C+Michaela%22">Seifrtová, Michaela</searchLink><relatesTo>1,3</relatesTo> (AUTHOR)<i> michaela.seifrtova@mff.cuni.cz</i>
– Name: TitleSource
  Label: Source
  Group: Src
  Data: <searchLink fieldCode="JN" term="%22Discrete+Applied+Mathematics%22">Discrete Applied Mathematics</searchLink>. May2026, Vol. 385, p194-221. 28p.
– Name: Subject
  Label: Subjects
  Group: Su
  Data: <searchLink fieldCode="DE" term="%22Computational+complexity%22">Computational complexity</searchLink><br /><searchLink fieldCode="DE" term="%22Multigraph%22">Multigraph</searchLink><br /><searchLink fieldCode="DE" term="%22NP-hard+problems%22">NP-hard problems</searchLink><br /><searchLink fieldCode="DE" term="%22Graph+theory%22">Graph theory</searchLink>
– Name: Abstract
  Label: Abstract
  Group: Ab
  Data: The notion of graph covers (also referred to as locally bijective homomorphisms) plays an important role in topological graph theory and has found its computer science applications in models of local computation. For a fixed target graph H , the H - Cover problem asks if an input graph G allows a graph covering projection onto H. Despite the fact that the quest for characterizing the computational complexity of H - Cover had been started more than 30 years ago, only a handful of general results have been known so far. In this paper, we present a complete characterization of the computational complexity of covering coloured graphs for the case that every equivalence class in the degree partition of the target graph has at most two vertices. We prove this result in a very general form. Following the lines of current development of topological graph theory, we study graphs in the most relaxed sense of the definition. In particular, we consider graphs that are mixed (they may have both directed and undirected edges), may have multiple edges, loops, and semi-edges. We show that a strong P/NP-complete dichotomy holds true in the sense that for each such fixed target graph H , the H - Cover problem is either polynomial-time solvable for arbitrary inputs, or NP-complete even for simple input graphs. [ABSTRACT FROM AUTHOR]
– Name: AbstractSuppliedCopyright
  Label:
  Group: Ab
  Data: <i>Copyright of Discrete Applied Mathematics is the property of Elsevier B.V. and its content may not be copied or emailed to multiple sites without the copyright holder's express written permission. Additionally, content may not be used with any artificial intelligence tools or machine learning technologies. However, users may print, download, or email articles for individual use. This abstract may be abridged. No warranty is given about the accuracy of the copy. Users should refer to the original published version of the material for the full abstract.</i> (Copyright applies to all Abstracts.)
PLink https://search.ebscohost.com/login.aspx?direct=true&site=eds-live&db=egs&AN=192194646
RecordInfo BibRecord:
  BibEntity:
    Identifiers:
      – Type: doi
        Value: 10.1016/j.dam.2026.01.019
    Languages:
      – Code: eng
        Text: English
    PhysicalDescription:
      Pagination:
        PageCount: 28
        StartPage: 194
    Subjects:
      – SubjectFull: Computational complexity
        Type: general
      – SubjectFull: Multigraph
        Type: general
      – SubjectFull: NP-hard problems
        Type: general
      – SubjectFull: Graph theory
        Type: general
    Titles:
      – TitleFull: Computational complexity of covering coloured mixed multigraphs with simple degree partitions.
        Type: main
  BibRelationships:
    HasContributorRelationships:
      – PersonEntity:
          Name:
            NameFull: Bok, Jan
      – PersonEntity:
          Name:
            NameFull: Fiala, Jiří
      – PersonEntity:
          Name:
            NameFull: Jedličková, Nikola
      – PersonEntity:
          Name:
            NameFull: Kratochvíl, Jan
      – PersonEntity:
          Name:
            NameFull: Seifrtová, Michaela
    IsPartOfRelationships:
      – BibEntity:
          Dates:
            – D: 31
              M: 05
              Text: May2026
              Type: published
              Y: 2026
          Identifiers:
            – Type: issn-print
              Value: 0166218X
          Numbering:
            – Type: volume
              Value: 385
          Titles:
            – TitleFull: Discrete Applied Mathematics
              Type: main
ResultId 1