Volume 16, No 6, 2009, P. 43-51
D. S. Malyshev
On minimal hard classes of graphs
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.
Keywords: computational complexity, minimal hard class, boundary class, recognition of hereditary property, list-ranking problems.
Malyshev Dmitry Sergeevich 1
1. Nizhegorodskiy State University,
23 Gagarin ave., bld. 2, 603950 N. Novgorod, Russia