EN|RU

Том 18, номер 3, 2011 г., Стр. 84-88

УДК 519.178
Малышев Д. С.
Анализ влияния числа рёбер в связных графах на трудоёмкость решения задачи о независимом множестве

Аннотация:
Изучается сложностной статус задачи о независимом множестве в классах связных графов, определяемых функциональными ограничениями числа рёбер от числа вершин. Показано, что для любого натурального $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.

Ключевые слова: вычислительная сложность, задача о независимом множестве.

Малышев Дмитрий Сергеевич 1
1. Национальный исследовательский университет «Высшая школа экономики» (Нижегородский филиал),
ул. Б. Печерская, 25/12, 603155 Нижний Новгород, Россия
е-mail: dsmalyshev@rambler.ru

Статья поступила 19 ноября 2010 г.
Исправленный вариант — 22 февраля 2011 г.

 © Институт математики им. С. Л. Соболева, 2015