Document Open Access Logo

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

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

PDF
Thumbnail PDF

File

LIPIcs.MFCS.2021.21.pdf
  • Filesize: 0.85 MB
  • 15 pages

Document Identifiers

Author Details

Jan Bok
  • Computer Science Institute, Faculty of Mathematics and Physics, Charles University, Prague, Czech Republic
Jiří Fiala
  • Department of Applied Mathematics, Faculty of Mathematics and Physics, Charles University, Prague, Czech Republic
Petr Hliněný
  • Faculty of Informatics, Masaryk University, Brno, Czech Republic
Nikola Jedličková
  • Department of Applied Mathematics, Faculty of Mathematics and Physics, Charles University, Prague, Czech Republic
Jan Kratochvíl
  • Department of Applied Mathematics, Faculty of Mathematics and Physics, Charles University, Prague, Czech Republic

Funding

  • Bok, Jan: Supported by research grant GAČR 20-15576S of the Czech Science Foundation and by SVV-2020-260578. The author was also partially supported by GAUK 1580119.
  • Fiala, Jiří: Supported by research grant GAČR 20-15576S of the Czech Science Foundation.
  • Hliněný, Petr: Supported by research grant GAČR 20-04567S of the Czech Science Foundation.
  • Jedličková, Nikola: Supported by research grant GAČR 20-15576S of the Czech Science Foundation and by SVV-2020-260578.
  • Kratochvíl, Jan: Supported by research grant GAČR 20-15576S of the Czech Science Foundation.

Cite As Get BibTex

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) https://doi.org/10.4230/LIPIcs.MFCS.2021.21

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

Subject Classification

ACM Subject Classification
  • Mathematics of computing → Graph theory
Keywords
  • graph cover
  • covering projection
  • semi-edges
  • multigraphs
  • complexity

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads
    0
    Metadata Views

Related Versions

References

  1. James Abello, Michael R. Fellows, and John C. Stillwell. On the complexity and combinatorics of covering finite complexes. Australian Journal of Combinatorics, 4:103-112, 1991. Google Scholar
  2. Dana Angluin. Local and global properties in networks of processors. Proceedings of the 12th ACM Symposium on Theory of Computing, pages 82-93, 1980. Google Scholar
  3. Dana Angluin and A. Gardiner. Finite common coverings of pairs of regular graphs. Journal of Combinatorial Theory B, 30:184-187, 1981. Google Scholar
  4. Dan Archdeacon. Two graphs without planar covers. Journal of Graph Theory, 41(4):318-326, 2002. Google Scholar
  5. Norman Biggs. Algebraic Graph Theory. Cambridge University Press, 1974. Google Scholar
  6. Ondřej Bílka, Jozef Jirásek, Pavel Klavík, Martin Tancer, and Jan Volec. On the complexity of planar covering of small graphs. In Petr Kolman and Jan Kratochvíl, editors, Graph-Theoretic Concepts in Computer Science, volume 6986 of Lecture Notes in Computer Science, pages 83-94. Springer, 2011. Google Scholar
  7. Hans L. Bodlaender. The classification of coverings of processor networks. Journal of Parallel Distributed Computing, 6:166-182, 1989. Google Scholar
  8. Jérémie Chalopin, Yves Métivier, and Wiesław Zielonka. Local computations in graphs: the case of cellular edge local computations. Fundamenta Informaticae, 74(1):85-114, 2006. Google Scholar
  9. Jérémie Chalopin and Daniël Paulusma. Graph labelings derived from models in distributed computing: A complete complexity classification. Networks, 58(3):207-231, 2011. Google Scholar
  10. Jérémie Chalopin and Daniël Paulusma. Packing bipartite graphs with covers of complete bipartite graphs. Discrete Applied Mathematics, 168:40-50, 2014. Google Scholar
  11. Steven Chaplick, Jiří Fiala, Pim van 't Hof, Daniël Paulusma, and Marek Tesař. Locally constrained homomorphisms on graphs of bounded treewidth and bounded degree. Theoretical Computer Science, 590:86-95, 2015. Google Scholar
  12. Derek G. Corneil. Graph Isomorphism. PhD thesis, University of Toronto, 1968. Google Scholar
  13. Derek G. Corneil and Calvin C. Gotlieb. An efficient algorithm for graph isomorphism. Journal of the Association for Computing Machinery, 17:51-64, 1970. Google Scholar
  14. Bruno Courcelle and Yves Métivier. Coverings and minors: Applications to local computations in graphs. European Journal of Combinatorics, 15:127-138, 1994. Google Scholar
  15. Dragomir Ž. Djoković. Automorphisms of graphs and coverings. Journal of Combinatorial Theory B, 16:243-247, 1974. Google Scholar
  16. Jiří Fiala and Jan Kratochvíl. Locally injective graph homomorphism: Lists guarantee dichotomy. In Fedor V. Fomin, editor, WG, volume 4271 of Lecture Notes in Computer Science, pages 15-26. Springer, 2006. Google Scholar
  17. Jiří Fiala. Locally injective homomorphisms. PhD thesis, Charles University, Prague, 2000. Google Scholar
  18. Jiří Fiala, Pinar Heggernes, Petter Kristiansen, and Jan Arne Telle. Generalized H-coloring and H-covering of trees. Nordic Journal of Computing, 10(3):206-224, 2003. Google Scholar
  19. Jiří Fiala, Pavel Klavík, Jan Kratochvíl, and Roman Nedela. Algorithmic aspects of regular graph covers with applications to planar graphs. In Javier Esparza, Pierre Fraigniaud, Thore Husfeldt, and Elias Koutsoupias, editors, ICALP (1), volume 8572 of Lecture Notes in Computer Science, pages 489-501. Springer, 2014. Google Scholar
  20. Jiří Fiala, Pavel Klavík, Jan Kratochvíl, and Roman Nedela. 3-connected reduction for regular graph covers. European Journal of Combinatorics, 73:170-210, 2018. Google Scholar
  21. Jiří Fiala and Jan Kratochvíl. Locally constrained graph homomorphisms - structure, complexity, and applications. Computer Science Review, 2(2):97-111, 2008. Google Scholar
  22. Jiří Fiala and Daniël Paulusma. A complete complexity classification of the role assignment problem. Theoretical Computer Science, 1(349):67-81, 2005. Google Scholar
  23. Jiří Fiala, Pavel Klavík, Jan Kratochvíl, and Roman Nedela. Algorithmic aspects of regular graph covers, 2016. URL: http://arxiv.org/abs/1609.03013.
  24. Anthony Gardiner. Antipodal covering graphs. Journal of Combinatorial Theory B, 16:255-273, 1974. Google Scholar
  25. Michael R. Garey and David S. Johnson. Computers and Intractability. W. H. Freeman and Co., New York, 1979. Google Scholar
  26. Ezra Getzler and Mikhail M Kapranov. Modular operads. Compositio Mathematica, 110(1):65-125, 1998. Google Scholar
  27. Jonathan L. Gross and Thomas W. Tucker. Generating all graph coverings by permutation voltage assignments. Discrete Mathematics, 18:273-283, 1977. Google Scholar
  28. Petr Hliněný. K_4,4-e has no finite planar cover. Journal of Graph Theory, 21(1):51-60, 1998. Google Scholar
  29. Petr Hliněný and Robin Thomas. On possible counterexamples to Negami’s planar cover conjecture. Journal of Graph Theory, 46(3):183-206, 2004. Google Scholar
  30. Jan Kratochvíl, Andrzej Proskurowski, and Jan Arne Telle. Covering directed multigraphs I. colored directed multigraphs. In Rolf H. Möhring, editor, WG, volume 1335 of Lecture Notes in Computer Science, pages 242-257. Springer, 1997. Google Scholar
  31. Jan Kratochvíl, Andrzej Proskurowski, and Jan Arne Telle. Covering directed multigraphs II. when 2-SAT helps. Technical Report 1997-354, KAM-DIMATIA Preprint Series, 1997. Google Scholar
  32. Jan Kratochvíl, Andrzej Proskurowski, and Jan Arne Telle. Covering regular graphs. Journal of Combinatorial Theory, Series B, 71(1):1-16, 1997. Google Scholar
  33. Jan Kratochvíl, Andrzej Proskurowski, and Jan Arne Telle. Complexity of graph covering problems. Nordic Journal of Computing, 5:173-195, 1998. Google Scholar
  34. Jan Kratochvíl, Jan Arne Telle, and Marek Tesař. Computational complexity of covering three-vertex multigraphs. Theoretical Computer Science, 609:104-117, 2016. Google Scholar
  35. Petter Kristiansen and Jan Arne Telle. Generalized H-coloring of graphs. In D. T. Lee and Shang-Hua Teng, editors, ISAAC, volume 1969 of Lecture Notes in Computer Science, pages 456-466. Springer, 2000. Google Scholar
  36. Jin Ho Kwak and Roman Nedela. Graphs and their coverings. Lecture Notes Series, 17, 2007. Google Scholar
  37. Frank Thomas Leighton. Finite common coverings of graphs. Journal of Combinatorial Theory B, 33:231-238, 1982. Google Scholar
  38. Daniel Leven and Zvi Galil. NP completeness of finding the chromatic index of regular graphs. Journal of Algorithms, 4:35-44, 1983. Google Scholar
  39. Igor Litovsky, Yves Métivier, and Wiesław Zielonka. The power and the limitations of local computations on graphs. In Ernst W. Mayr, editor, WG, volume 657 of Lecture Notes in Computer Science, pages 333-345. Springer, 1992. Google Scholar
  40. Laszló Lovász and Michael. D. Plummer. Matching Theory. Akadémiai Kiadó, Budapest, 1986. Google Scholar
  41. Gary MacGillivray and Jacobus Swarts. The complexity of locally injective homomorphisms. Discrete Mathematics, 310(20):2685-2696, 2010. Graph Theory - Dedicated to Carsten Thomassen on his 60th Birthday. Google Scholar
  42. Aleksander Malnič, Dragan Marušič, and Primož Potočnik. Elementary abelian covers of graphs. Journal of Algebraic Combinatorics, 20(1):71-97, 2004. Google Scholar
  43. Aleksander Malnič, Roman Nedela, and Martin Škoviera. Lifting graph automorphisms by voltage assignments. European Journal of Combinatorics, 21(7):927-947, 2000. Google Scholar
  44. Alexander D. Mednykh and Roman Nedela. Harmonic Morphisms of Graphs: Part I: Graph Coverings. Vydavatelstvo Univerzity Mateja Bela v Banskej Bystrici, 1st edition, 2015. Google Scholar
  45. Roman Nedela and Martin Škoviera. Regular embeddings of canonical double coverings of graphs. Journal of Combinatorial Theory, Series B, 67(2):249-277, 1996. Google Scholar
  46. Seiya Negami. Graphs which have no planar covering. Bulletin of the Institute of Mathematics, Academia Sinica, 16(4):377-384, 1988. Google Scholar
  47. Julius Petersen. Die theorie der regulären graphs. Acta Mathematica, 15:193-220, 1891. Google Scholar
  48. Gerhard Ringel. Map color theorem, volume 209. Springer, Berlin, 1974. Google Scholar
  49. Sam Shepherd, Giles Gardam, and Daniel J. Woodhouse. Two generalisations of Leighton’s theorem, 2019. URL: http://arxiv.org/abs/1908.00830.
  50. David R. Wood. Defective and clustered graph colouring. Electronic Journal of Combinatorics, 2018. URL: https://doi.org/10.37236/7406.
  51. Daniel J. Woodhouse. Revisiting Leighton’s theorem with the Haar measure, 2018. URL: http://arxiv.org/abs/1806.08196.
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact