Critical graph classes for the edge list-ranking problem

The edge list-ranking problem is a model for some parallel processes. We study the computational complexity of this problem for graph sets closed under isomorphism and deletion of vertices (hereditary classes). We describe all finitely defined and minor-closed cases for which the problem is polynomial-time solvable. We find the whole set of “critical” graph classes, the inclusion of which in a finitely defined class is equivalent to intractability of the edge list-ranking problem in this class. It seems to be the first result on a complete description for non-artificial NP-complete graph problems. For this problem, we constructively prove that among minimal under inclusion NP-complete hereditary cases there are exactly 5 finitely defined classes and exactly 1 minor-closed class. Ill. 1, bibliogr. 13.