Volume 20, No 6, 2013, P. 5976
UDC 519.178
Malyshev D. S.
Critical graph classes for the edge listranking problem
Abstract:
The edge listranking problem is a generalization of the classical edge coloring problem and it is a mathematical 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 minorclosed cases for which the problem is polynomialtime 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 listranking problem in this class. It seems to be the first result on a complete description for nonartificial NPcomplete graph problems. For this problem, we constructively prove that among minimal under inclusion NPcomplete hereditary cases there are exactly 5 finitely defined classes and exactly 1 minorclosed class.
Ill. 1, bibliogr. 13.
Keywords: computational complexity, hereditary class, boundary class, minimal hard class, polynomial algorithm, edge listranking problem.
Malyshev Dmitriy Sergeevich^{ 1,2}
1. Nizhniy Novgorod Higher School of Economics,
25/12 B. Pecherskaya St., 603155 Nizhniy Novgorod, Russia
2.
Nizhniy Novgorod State University,
23 Gagarin Ave., 603950 Nizhniy Novgorod, Russia
email: dsmalyshev@rambler.ru
