Abstract
A covering projection from a graph G to a graph H is a mapping of the vertices of G to the vertices of H such that, for every vertex v of G, the neighborhood of v is mapped bijectively to the neighborhood of its image. Moreover, if G and H are multigraphs, then this local bijection has to preserve multiplicities of the neighbors as well. The notion of covering projection stems from topology, but has found applications in areas such as the theory of local computation and construction of highly symmetric graphs. It provides a restrictive variant of the constraint satisfaction problem with additional symmetry constraints on the behavior of the homomorphisms of the structures involved.
We investigate the computational complexity of the problem of deciding the existence of a covering projection from an input graph G to a fixed target graph H. Among other partial results this problem has been shown to be NP-hard for simple regular graphs H of valency greater than 2, and a full characterization of computational complexity has been shown for target multigraphs with 2 vertices. We extend the previously known results to the ternary case, i.e., we give a full characterization of the computational complexity in the case of multigraphs with 3 vertices. We show that even in this case a P/NP-completeness dichotomy holds.
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
Abello, J., Fellows, M.R., Stillwell, J.C.: On the complexity and combinatorics of covering finite complexes. Australian Journal of Combinatorics 4, 103–112 (1991)
Angluin, D.: Local and global properties in networks of processors. In: Proceedings of the 12th ACM Symposium on Theory of Computing, pp. 82–93 (1980)
Angluin, D., Gardiner, A.: Finite common coverings of pairs of regular graphs. Journal of Combinatorial Theory, Series B 30(2), 184–187 (1981)
Bodlaender, H.L.: The Classification of Coverings of Processor Networks. Journal of Parallel and Distributed Computing 6, 166–182 (1989)
Bulatov, A.A.: A dichotomy theorem for constraint satisfaction problems on a 3-element set. J. ACM 53(1), 66–120 (2006)
Corneil, D.G., Gotlieb, C.C.: An Efficient Algorithm for Graph Isomorphism. J. ACM 17(1), 51–64 (1970)
Courcelle, B., Métivier, Y.: Coverings and Minors: Application to Local Computations in Graphs. European Journal of Combinatorics 15(2), 127–138 (1994)
Feder, T., Vardi, M.Y.: The computational structure of monotone monadic SNP and constraint satisfaction: a study through Datalog and group theory. SIAM Journal of Computing 1, 57–104 (1998)
Fiala, J., Kratochvíl, J.: Locally constrained graph homomorphisms-structure, complexity, and applications. Computer Science Review 2, 97–111 (2008)
Hell, P., Nešetřil, J.: Graphs and Homomorphisms. Oxford University Press (2004)
Hliněný, P.: K 4,4 − e Has No Finite Planar Cover. Journal of Graph Theory 21(1), 51–60 (1998)
Hliněný, P., Thomas, R.: On possible counterexamples to Negami’s planar cover conjecture. Journal of Graph Theory 46(3), 183–206 (2004)
Holyer, I.: The NP-Completeness of Edge-Coloring. SIAM J. Comput. 10(4), 718–720 (1981)
Kratochvíl, J.: Complexity of Hypergraph Coloring and Seidel’s Switching. In: Bodlaender, H.L. (ed.) WG 2003. LNCS, vol. 2880, pp. 297–308. Springer, Heidelberg (2003)
Kratochvíl, J., Proskurowski, A., Telle, J.A.: Covering Regular Graphs. Journal of Combinatorial Theory, Series B 71(1), 1–16 (1997)
Kratochvíl, J., Proskurowski, A., Telle, J.A.: Complexity of colored graph covers I. Colored directed multigraphs. In: Möhring, R.H. (ed.) WG 1997. LNCS, vol. 1335, pp. 242–257. Springer, Heidelberg (1997)
Kratochvíl, J., Proskurowski, A., Telle, J.A.: Complexity of graph covering problems. Nordic Journal of Computing 5, 173–195 (1998)
Litovsky, I., Métivier, Y., Zielonka, W.: The power and the limitations of local computations on graphs. In: Mayr, E.W. (ed.) WG 1992. LNCS, vol. 657, pp. 333–345. Springer, Heidelberg (1993)
Negami, S.: Graphs which have no planar covering. Bulletin of the Institute of Mathematics, Academia Sinica 4, 377–384 (1988)
Schaefer, T.J.: The complexity of satisfiability problems. In: Proceedings of the Tenth Annual ACM Symposium on Theory of Computing, STOC 1978, pp. 216–226 (1978)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2014 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Kratochvíl, J., Telle, J.A., Tesař, M. (2014). Computational Complexity of Covering Three-Vertex Multigraphs. In: Csuhaj-Varjú, E., Dietzfelbinger, M., Ésik, Z. (eds) Mathematical Foundations of Computer Science 2014. MFCS 2014. Lecture Notes in Computer Science, vol 8635. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-662-44465-8_42
Download citation
DOI: https://doi.org/10.1007/978-3-662-44465-8_42
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-662-44464-1
Online ISBN: 978-3-662-44465-8
eBook Packages: Computer ScienceComputer Science (R0)