Volume 18, No 3, 2011, P. 8488
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\colonV(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\colonV(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
email: dsmalyshev@rambler.ru
