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 Cet article a éte moissonné depuis la source Math-Net.Ru

Voir la notice de l'article

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},
     year = {2011},
     volume = {18},
     number = {3},
     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
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
%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