Том 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. Национальный исследовательский университет «Высшая школа экономики» (Нижегородский филиал),
ул. Б. Печерская, 25/12, 603155 Нижний Новгород, Россия
е-mail: dsmalyshev@rambler.ru

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

Литература

[1] Малышев Д. С. Совместное влияние количества рёбер и компонент связности в графах на сложность вычисления числа независимости // Материалы Российской конференции «Дискретная оптимизация и исследование операций» (Республика Алтай, 2010 г.). — Новосибирск: Ин-т математики, 2010. — С. 136.

[2] Ахо А., Хопкрофт Дж., Ульман Дж. Построение и анализ вычислительных алгоритмов. — М.: Мир, 1979. — 536 c.

[3] Impagliazzo R., Paturi R. Which problems have strongly exponentional complexity? //J. Comput. Syst. Sci. — 2001. — Vol. 62. — P. 512–530.