• A
  • A
  • A
  • АБB
  • АБB
  • АБB
  • А
  • А
  • А
  • А
  • А
Обычная версия сайта

Статья

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

Изучается сложностной статус задачи о независимом множестве в классах связных графов, определяемых функциональными ограничениями числа ребер от числа вершин. Показано, что для любого натурального C в классе графов  ∞Sn=1{G | |V (G)| = n,|E(G)| 6 n + C[log2(n)]} эта задача полиномиально разрешима. С другой стороны, доказано, что она не является полиномиально разрешимой в классе графов  ∞Sn=1{G | |V (G)| = n,|E(G)| 6 n + C[log2(n)]}  для любой неограниченной неубывающей функции f(n) : N → N, экспонента от которой растет быстрее, чем полином от n. Последний результат справедлив, если для задачи о независимом множестве нет субэкспоненциальных алгоритмов.