Volume 16, No 6, 2009, P. 43-51

UDC 519.178
D. S. Malyshev
On minimal hard classes of graphs

Abstract:
We consider the notions of a minimal hard class of graphs and a boundary class of graphs. We prove that there is no minimal hard classes for problem of recognition belonging to a hereditary class. We point out boundary and minimal hard classes of graphs for the list-ranking problems. These classes of graphs are the first examples of minimal hard classes and the first examples of hard boundary classes.
Bibl. 9.

Keywords: computational complexity, minimal hard class, boundary class, recognition of hereditary property, list-ranking problems.

Malyshev Dmitry Sergeevich ¹
1. Nizhegorodskiy State University,
23 Gagarin ave., bld. 2, 603950 N. Novgorod, Russia
e-mail: dsmalyshev@rambler.ru