Volume 19, No 1, 2012, P. 7496
UDC 519.178
D. S. Malyshev
The complexity analysis of the edgeranking problem for hereditary graph classes with at most three prohibitions
Abstract:
We completely characterize all hereditary classes defined by at most three forbidden induced subgraphs (obstructions) for which the edge listranking problem is polynomialtime solvable. For each class in this family, the algorithm of determining the complexity status of the problem in the class is based on checking whether or not the obstructions belong to some special (“critical”) classes of graphs. The family of such special classes includes, in particular, inclusionwise minimal classes for which the problem is NPcomplete. All classes of this type defined by at most three obstructions are described.
Ill. 3, bibliogr. 14.
Keywords: computational complexity, minimal hard class, boundary class, edge listranking problem, polynomial algorithm.
Malyshev Dmitrii Sergeevich ^{1,2}
1. Nizhniy Novgorod State University,
23 Gagarina ave., 603950 Nizhniy Novgorod, Russia
2.
Nizhniy Novgorod branch of Higher School of Economics,
25/12 B. Pecherskaya str., 603155 Nizhniy Novgorod, Russia
email: dsmalyshev@rambler.ru
