EN|RU Volume 18, No 3, 2011, P. 84-88 UDC 519.178 D. S. Malyshev Analysis of the number of the edges effect on the complexity of the independent set problem solvability Abstract: We consider classes of connected graphs, defined by functional constraints of the number of the edges depending on the vertex quantity. We show that for any fixed $C$ this problem is polynomially solvable in the class $\bigcup_{n=1}^\infty\{G\colon|V(G)|=n,\,|E(G)|\leq n+C[\log_2(n)]\}$. From the other hand, we prove that this problem isn't polynomial in the class $\bigcup_{n=1}^\infty\{G\colon|V(G)|=n,\,|E(G)|\leq n+f^2(n)\}$, providing $f(n)\colon\mathbb N\to\mathbb N$ is unbounded and nondecreasing and an exponent of $f(n)$ grows faster than a polynomial of $n$. The last result holds if there is no subexponential algorithms for solving of the independent set problem. Bibliogr. 3. Keywords: computational complexity, independent set problem. Malyshev Dmitrii Sergeevich 1,2 1. Nizhniy Novgorod branch of Higher School of Economics, 25/12 B. Pecherskaya str., 603155 Nizhny Novgorod, Russia 2. Nizhniy Novgorod State University, 23 Gagarina ave., 603950 Nizhniy Novgorod, Russia e-mail: dsmalyshev@rambler.ru © Sobolev Institute of Mathematics, 2015