DROPS

Document

DOI: 10.4230/LIPIcs.MFCS.2021.21

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

Authors: Jan Bok, Jiří Fiala, Petr Hliněný, Nikola Jedličková, and Jan Kratochvíl

Published in: LIPIcs, Volume 202, 46th International Symposium on Mathematical Foundations of Computer Science (MFCS 2021)

Abstract

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

Cite as

Jan Bok, Jiří Fiala, Petr Hliněný, Nikola Jedličková, and Jan Kratochvíl. Computational Complexity of Covering Multigraphs with Semi-Edges: Small Cases. In 46th International Symposium on Mathematical Foundations of Computer Science (MFCS 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 202, pp. 21:1-21:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)

Copy BibTex To Clipboard

@InProceedings{bok_et_al:LIPIcs.MFCS.2021.21,
  author =	{Bok, Jan and Fiala, Ji\v{r}{\'\i} and Hlin\v{e}n\'{y}, Petr and Jedli\v{c}kov\'{a}, Nikola and Kratochv{\'\i}l, Jan},
  title =	{{Computational Complexity of Covering Multigraphs with Semi-Edges: Small Cases}},
  booktitle =	{46th International Symposium on Mathematical Foundations of Computer Science (MFCS 2021)},
  pages =	{21:1--21:15},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-201-3},
  ISSN =	{1868-8969},
  year =	{2021},
  volume =	{202},
  editor =	{Bonchi, Filippo and Puglisi, Simon J.},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.MFCS.2021.21},
  URN =		{urn:nbn:de:0030-drops-144611},
  doi =		{10.4230/LIPIcs.MFCS.2021.21},
  annote =	{Keywords: graph cover, covering projection, semi-edges, multigraphs, complexity}
}

Document

DOI: 10.4230/LIPIcs.ESA.2020.22

Acyclic, Star and Injective Colouring: A Complexity Picture for H-Free Graphs

Authors: Jan Bok, Nikola Jedlic̆ková, Barnaby Martin, Daniël Paulusma, and Siani Smith

Published in: LIPIcs, Volume 173, 28th Annual European Symposium on Algorithms (ESA 2020)

Abstract

A k-colouring c of a graph G is a mapping V(G) → {1,2,… k} such that c(u) ≠ c(v) whenever u and v are adjacent. The corresponding decision problem is Colouring. A colouring is acyclic, star, or injective if any two colour classes induce a forest, star forest or disjoint union of vertices and edges, respectively. Hence, every injective colouring is a star colouring and every star colouring is an acyclic colouring. The corresponding decision problems are Acyclic Colouring, Star Colouring and Injective Colouring (the last problem is also known as L(1,1)-Labelling). A classical complexity result on Colouring is a well-known dichotomy for H-free graphs, which was established twenty years ago (in this context, a graph is H-free if and only if it does not contain H as an induced subgraph). Moreover, this result has led to a large collection of results, which helped us to better understand the complexity of Colouring. In contrast, there is no systematic study into the computational complexity of Acyclic Colouring, Star Colouring and Injective Colouring despite numerous algorithmic and structural results that have appeared over the years. We initiate such a systematic complexity study, and similar to the study of Colouring we use the class of H-free graphs as a testbed. We prove the following results: 1) We give almost complete classifications for the computational complexity of Acyclic Colouring, Star Colouring and Injective Colouring for H-free graphs. 2) If the number of colours k is fixed, that is, not part of the input, we give full complexity classifications for each of the three problems for H-free graphs. From our study we conclude that for fixed k the three problems behave in the same way, but this is no longer true if k is part of the input. To obtain several of our results we prove stronger complexity results that in particular involve the girth of a graph and the class of line graphs.

Cite as

Jan Bok, Nikola Jedlic̆ková, Barnaby Martin, Daniël Paulusma, and Siani Smith. Acyclic, Star and Injective Colouring: A Complexity Picture for H-Free Graphs. In 28th Annual European Symposium on Algorithms (ESA 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 173, pp. 22:1-22:22, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)

Copy BibTex To Clipboard

@InProceedings{bok_et_al:LIPIcs.ESA.2020.22,
  author =	{Bok, Jan and Jedlic̆kov\'{a}, Nikola and Martin, Barnaby and Paulusma, Dani\"{e}l and Smith, Siani},
  title =	{{Acyclic, Star and Injective Colouring: A Complexity Picture for H-Free Graphs}},
  booktitle =	{28th Annual European Symposium on Algorithms (ESA 2020)},
  pages =	{22:1--22:22},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-162-7},
  ISSN =	{1868-8969},
  year =	{2020},
  volume =	{173},
  editor =	{Grandoni, Fabrizio and Herman, Grzegorz and Sanders, Peter},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ESA.2020.22},
  URN =		{urn:nbn:de:0030-drops-128885},
  doi =		{10.4230/LIPIcs.ESA.2020.22},
  annote =	{Keywords: acyclic colouring, star colouring, injective colouring, H-free, dichotomy}
}

Document

DOI: 10.4230/LIPIcs.MFCS.2020.20

List Homomorphism Problems for Signed Graphs

Authors: Jan Bok, Richard Brewster, Tomás Feder, Pavol Hell, and Nikola Jedličková

Published in: LIPIcs, Volume 170, 45th International Symposium on Mathematical Foundations of Computer Science (MFCS 2020)

Abstract

We consider homomorphisms of signed graphs from a computational perspective. In particular, we study the list homomorphism problem seeking a homomorphism of an input signed graph (G,σ), equipped with lists L(v) ⊆ V(H), v ∈ V(G), of allowed images, to a fixed target signed graph (H,π). The complexity of the similar homomorphism problem without lists (corresponding to all lists being L(v) = V(H)) has been previously classified by Brewster and Siggers, but the list version remains open and appears difficult. Both versions (with lists or without lists) can be formulated as constraint satisfaction problems, and hence enjoy the algebraic dichotomy classification recently verified by Bulatov and Zhuk. By contrast, we seek a combinatorial classification for the list version, akin to the combinatorial classification for the version without lists completed by Brewster and Siggers. We illustrate the possible complications by classifying the complexity of the list homomorphism problem when H is a (reflexive or irreflexive) signed tree. It turns out that the problems are polynomial-time solvable for certain caterpillar-like trees, and are NP-complete otherwise. The tools we develop will be useful for classifications of other classes of signed graphs, and we mention some follow-up research of this kind; those classifications are surprisingly complex.

Cite as

Jan Bok, Richard Brewster, Tomás Feder, Pavol Hell, and Nikola Jedličková. List Homomorphism Problems for Signed Graphs. In 45th International Symposium on Mathematical Foundations of Computer Science (MFCS 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 170, pp. 20:1-20:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)

Copy BibTex To Clipboard

@InProceedings{bok_et_al:LIPIcs.MFCS.2020.20,
  author =	{Bok, Jan and Brewster, Richard and Feder, Tom\'{a}s and Hell, Pavol and Jedli\v{c}kov\'{a}, Nikola},
  title =	{{List Homomorphism Problems for Signed Graphs}},
  booktitle =	{45th International Symposium on Mathematical Foundations of Computer Science (MFCS 2020)},
  pages =	{20:1--20:14},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-159-7},
  ISSN =	{1868-8969},
  year =	{2020},
  volume =	{170},
  editor =	{Esparza, Javier and Kr\'{a}l', Daniel},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.MFCS.2020.20},
  URN =		{urn:nbn:de:0030-drops-126886},
  doi =		{10.4230/LIPIcs.MFCS.2020.20},
  annote =	{Keywords: complexity, dichotomy, graph homomorphism, signed graph}
}

3 Search Results for "Jedličková, Nikola"

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

Abstract

Cite as

Acyclic, Star and Injective Colouring: A Complexity Picture for H-Free Graphs

Abstract

Cite as

List Homomorphism Problems for Signed Graphs

Abstract

Cite as

Thanks for your feedback!

Could not send message