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

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