Анализ влияния числа рёбер в связных графах на трудоёмкость решения задачи о независимом множестве

Изучается сложностной статус задачи о независимом множестве в классах связных графов, определяемых функциональными ограничениями числа рёбер от числа вершин. Показано, что для любого натурального $C$ в классе графов $\bigcup_{n=1}^\infty\{G\mid|V(G)|=n$, $|E(G)|\leq n+C[\log_2(n)]\}$ эта задача полиномиально разрешима. С другой стороны, доказано, что она не является полиномиально разрешимой в классе графов $\bigcup_{n=1}^\infty\{G\mid|V(G)|=n,\,|E(G)|\leq n+f^2(n)\}$ для любой неограниченной неубывающей функции $f(n)\colon\mathbb N\to\mathbb N$, экспонента от которой растёт быстрее, чем полином от $n$. Последний результат справедлив, если для задачи о независимом множестве нет субэкспоненциальных алгоритмов. Библиогр. 3.