Abello, James; Fellows, Michael R.; Stillwell, John C. On the complexity and combinatorics of covering finite complexes. (English) Zbl 0763.05035 Australas. J. Comb. 4, 103-112 (1991). The computational complexity of covering projections of finite complexes is considered. As the main result, it is proved that there exist graphs (that is, 1-complexes) \(H\) for which the decision problem which takes as input a finite graph \(G\) and determines if there is a covering projection of \(H\) by \(G\) is NP-complete (both in simplicial as well as in topological setting). This is interesting because the existence of a covering projection establishes a “local isomorphism” between graphs, and so the problem of its detecting seems to be substantially different from isomorphism testing. Some results on pairs of infinite 1-complexes that are each other’s covering spaces are included. Reviewer: A.Rosa (Hamilton / Ontario) Cited in 27 Documents MSC: 05C10 Planar graphs; geometric and topological aspects of graph theory 68Q15 Complexity classes (hierarchies, relations among complexity classes, etc.) 68R15 Combinatorics on words Keywords:simplicial complex; computational complexity; covering projections PDF BibTeX XML Cite \textit{J. Abello} et al., Australas. J. Comb. 4, 103--112 (1991; Zbl 0763.05035) OpenURL