Задача про незалежну множину

Задача про незалежну множину належить до класу NP-повних задач в області теорії графів. Еквівалентна задачі про кліку.

Визначення

Незалежний набір з 9 блакитних вершин

Множина вершин графу називається незалежною, якщо ніякі дві вершини цієї множини не з'єднані ребром. Іншими словами, індукований цією множиною підграф складається з ізольованих вершин. Іноді також говорять, що кожне ребро графу інцидентне не більше ніж одній вершині з незалежної множини. Задача розпізнавання (Проблема вибору) виглядає так: чи існує в заданому графі G незалежна множина розміру k? Відповідна їй оптимізаційна задача, вона ж задача про незалежну множину, формулюється таким чином: в заданому графі G потрібно знайти незалежну множину максимального розміру. Цей розмір називають число́м незале́жності або число́м вну́трішньої щі́льності і позначають як α(G).

Іноді цю задачу називають пошуком незалежної множини максимального розміру або максимальної (за розміром) незалежної множини. Не варто плутати це поняття з максимальною (по включенню) незалежною множиною, яка визначається як така незалежна множина вершин, що при додаванні до неї ще однієї (будь-якої) вершини початкового графу вона перестає бути незалежною. Зрозуміло, що таких множин, взагалі кажучи, може бути декілька і різних розмірів. Максимальною по включенню незалежна множина аж ніяк не завжди є максимальною за розміром. У той же час, кожна незалежна множина максимального розміру за визначенням є також і максимальною по включенню. Для знаходження (якоїсь) максимальної по включенню незалежної множини можна скористатися жадібним алгоритмом, який виконується за поліноміальний час, тоді як задача про незалежну множину максимального розміру належить до класу NP-повних задач.

Максимальна незалежна множина в дереві

Якщо даний граф є деревом, то завдання про незалежну множину ефективно вирішується методом динамічного програмування.

Оптимальна підструктура задач

Структура дерева сама підказує рішення задачі: Позначимо коренем дерева будь-яку вершину і назвемо її ${\displaystyle r}$. Нехай ${\displaystyle I(u)}$ позначає розмір максимальної незалежної множини вершин піддерева, коренем якого є вершина ${\displaystyle u}$. Тоді відповіддю на задачу буде ${\displaystyle I(r)}$.

Неважко бачити, що якщо ми включаємо вершину u в максимальну незалежну множину, то її потужність збільшується на 1, але його дітей ми брати не можемо (так як вони з'єднані ребром з вершиною u); якщо ж ми не включаємо цю вершину, то потужність максимальної незалежної множини дорівнюватиме сумі розмірів незалежних множин дітей цієї вершини. Залишається тільки вибрати максимум з цих двох варіантів, щоб отримати рішення задачі:

${\displaystyle I(u)=\max \left\{1\ +\ \sum _{{\text{grandchild}}\ w\ of\ u}I(w),\ \sum _{{\text{child}}\ w\ of\ u}I(w)\right\},}$

де grandchild позначає всякого «онука» вершини, а child позначає всякого нащадка вершини.

Псевдокод

Вважаємо, що у вершині u зберігається ${\displaystyle I(u)}$:

 function get_independent_set(Node u) { якщо I(u) вже пораховане, то повернути I(u) //потужність множини, яку можна отримати, якщо не брати вершину u children_sum = 0 //потужність множини, яку можна отримати, якщо взяти вершину u grandchildren_sum = 0 //цикл по всім дітям for i := 1 to child_num do children_sum = children_sum + get_independent_set(children[i]) //цикл по всіх онукам for i:= 1 to grandchildren_num grandchildren_sum = grandchildren_sum + get_independent_set(grandchildren[i]) //запам'ятовуємо, щоб не перераховувати ще раз I(u) = max(1 + grandchildren_sum, children_sum) повернути I(u) } 

Виклик get_independent_set(r) дасть відповідь на завдання. Час виконання алгоритму, очевидно, O(|V| + |E|).

Література

• Godsil, Chris; Gordon Royle (2004) [1949]. Algebraic Graph Theory. New York: Springer. ISBN .

• Richard Karp (1972). Reducibility Among Combinatorial Problems. Proceedings of a Symposium on the Complexity of Computer Computations.

• Michael R. Garey, David S. Johnson (1979). Computers and Intractability: A Guide to the Theory of NP-Completeness. W.H. Freeman. . A1.2: GT20, pg.194.

• Moon, J. W.; Moser, L. (1965), On cliques in graphs, Israel J. Math., 3: 23—28, MR0182577

• Sanjoy Dasgupta, Christos H. Papadimitriou, Umesh Vazirani. Algorithms. — 1-е вид. — McGraw-Hill Science/Engineering/Math, 2006. — С. 336. — .

Див. також

• (Алгоритм Брона-Кербоша) для знаходження максимальних по включенню незалежних множин вершин.

Посилання

• Weisstein, Eric W. Maximal Independent Vertex Set(англ.) на сайті Wolfram MathWorld.
• Challenging Benchmarks for Maximum Clique, Maximum Independent Set, Minimum Vertex Cover and Vertex Coloring [ 29 травня 2013 у Wayback Machine.]
• Полікарпова Н., Герасименко А.
• Слайди лекції по динамічному програмуванні [ 19 квітня 2009 у Wayback Machine.]