Geodesic
Analysis of the number of the edges effect on the complexity of the independent set problem solvability
Diskretnyj analiz i issledovanie operacij, Tome 18 (2011) no. 3, pp. 84-88.

Voir la notice de l'article provenant de la source Math-Net.Ru

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. 
@article{DA_2011_18_3_a7,
     author = {D. S. Malyshev},
     title = {Analysis of the number of the edges effect on the complexity of the independent set problem solvability},
     journal = {Diskretnyj analiz i issledovanie operacij},
     pages = {84--88},
     publisher = {mathdoc},
     volume = {18},
     number = {3},
     year = {2011},
     language = {ru},
     url = {http://geodesic.mathdoc.fr/item/DA_2011_18_3_a7/}
}
TY  - JOUR
AU  - D. S. Malyshev
TI  - Analysis of the number of the edges effect on the complexity of the independent set problem solvability
JO  - Diskretnyj analiz i issledovanie operacij
PY  - 2011
SP  - 84
EP  - 88
VL  - 18
IS  - 3
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/DA_2011_18_3_a7/
LA  - ru
ID  - DA_2011_18_3_a7
ER  - 
%0 Journal Article
%A D. S. Malyshev
%T Analysis of the number of the edges effect on the complexity of the independent set problem solvability
%J Diskretnyj analiz i issledovanie operacij
%D 2011
%P 84-88
%V 18
%N 3
%I mathdoc
%U http://geodesic.mathdoc.fr/item/DA_2011_18_3_a7/
%G ru
%F DA_2011_18_3_a7
D. S. Malyshev. Analysis of the number of the edges effect on the complexity of the independent set problem solvability. Diskretnyj analiz i issledovanie operacij, Tome 18 (2011) no. 3, pp. 84-88. http://geodesic.mathdoc.fr/item/DA_2011_18_3_a7/

[1] Malyshev D. S., “Sovmestnoe vliyanie kolichestva rëber i komponent svyaznosti v grafakh na slozhnost vychisleniya chisla nezavisimosti”, Materialy Rossiiskoi konferentsii “Diskretnaya optimizatsiya i issledovanie operatsii” (Respublika Altai, 2010 g.), In-t matematiki, Novosibirsk, 2010, 136

[2] Akho A., Khopkroft Dzh., Ulman Dzh., Postroenie i analiz vychislitelnykh algoritmov, Mir, M., 1979, 536 pp. | MR

[3] Impagliazzo R., Paturi R., “Which problems have strongly exponentional complexity”, J. Comput. Syst. Sci., 62 (2001), 512–530 | DOI | MR