Задача о независимом множестве: различия между версиями

 
Задача о независимом множестве и [[задача о клике]] являются двойственными: клика в ''G'' — это независимое множество в [[Дополнение графа|дополнении графа]] ''G'' и наоборот. Таким образом, многие вычислительные результаты могут быть приложены одинаково хорошо к обоим задачам. Например, результаты, связанные с задачей о клике, имеют следующие следствия:
* Задача о наличии является [[NP-полная задача|NP-полной]], а это означает, что существование (ровно как и не существование) эффективного алгоритма её решения не доказано. Существует эффективные эвристические алгоритмы поиска максимального по весу независимого множества вершин в графе, примером которых может служить [https://elibrary.ru/item.asp?id=30374851 алгоритм Русова В.С. и Захаровой Д.А.] имеющий сложность O(''n''<sup>3</sup>).
* Задача о наибольшем максимальном множестве [[NP-полная задача|NP-трудна]] и её, кроме того, трудно [[Аппроксимационный алгоритм|аппроксимировать]].
 
Анонимный участник