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

Abello, James; Fellows, Michael R.; Stillwell, John C.

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)

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