On the complexity and combinatorics of covering finite complexes. (English) Zbl 0763.05035

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.


05C10 Planar graphs; geometric and topological aspects of graph theory
68Q15 Complexity classes (hierarchies, relations among complexity classes, etc.)
68R15 Combinatorics on words