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