Задача о независимом множестве

Материал из Википедии — свободной энциклопедии
Перейти к: навигация, поиск

Задача о независимом множестве относится к классу NP-полных задач в области теории графов. Эквивалентна задаче о клике.

Определения[править | править вики-текст]

Независимый набор из 9 голубых вершин

Множество вершин графа называется независимым, если никакие две вершины этого множества не соединены ребром. Другими словами, индуцированный этим множеством подграф состоит из изолированных вершин. Иногда также говорят, что каждое ребро графа инцидентно не более чем одной вершине из независимого множества. Задача распознавания (англ.) (Проблема разрешимости) выглядит так: существует ли в заданном графе G независимое множество размера k? Соответствующая ей оптимизационная задача, она же задача о независимом множестве, формулируется следующим образом: в заданном графе G требуется найти независимое множество максимального размера. Этот размер называют числом независимости, числом внутренней плотности или неплотностью и обозначают как α(G)[1][2].

Иногда эту задачу называют поиском независимого множества максимального размера или максимального (по размеру) независимого множества. Не стоит путать это понятие с максимальным (по включению) независимым множеством, которое определяется как такое независимое множество вершин, что при добавлении к нему ещё одной (любой) вершины исходного графа оно перестает быть независимым. Понятно, что таких множеств, вообще говоря, может быть несколько и разных размеров. Максимальное по включению независимое множество отнюдь не всегда является максимальным по размеру. В то же время, каждое независимое множество максимального размера по определению является также и максимальным по включению. Для нахождения (какого-то) максимального по включению независимого множества можно воспользоваться жадным алгоритмом, работающим за полиномиальное время, тогда как задача о независимом множестве максимального размера принадлежит к классу NP-полных задач.

Максимальное по включению независимое множество называют также наибольшим. Наибольшее независимое множество является доминирующим множеством[en]. Любой граф содержит максимум 3n/3 наибольших независимых множеств[3], однако большая часть графов имеет их куда меньше.

Число наибольших независимых множеств в циклах из n вершин — это числа Перрина, а число наибольших независимых множеств в путях с n вершинами задаётся последовательностью Падована[4]. Таким образом, оба числа пропорциональны степени 1.324718, пластическому числу.

Связь с другими параметрами графов[править | править вики-текст]

Множество независимо тогда и только тогда, кода оно является кликой в дополнении графа, так что два понятия дополняют друг друга. Достаточно большие графы без больших клик имеют большие независимые множества, что является предметом исследования в теории Рамсея.

Множество независимо тогда и только тогда, когда его дополнение является вершинным покрытием. Сумма α(G) и размера минимального вершинного покрытия β(G) равна числу вершин графа.

раскраска вершин графа G соответствует разбиению его вершин на независимые подмножества. Поэтому минимальное число красок, требующихся для раскраски вершин, хроматическое число χ(G), не меньше частного от деления числа вершин G и числа независимости α(G).

В двудольных графах, не имеющих изолированных вершин, число вершин в максимальном независимом множестве равно числу рёбер в минимальном рёберном покрытии (теорема Кёнига).

Поиск независимых множеств[править | править вики-текст]

В информатике изучается несколько вычислительных задач[en], связанных с независимыми множествами.

  • В задаче о максимальном независимом множестве входом служит неориентированный граф, а выходом – максимальное независимое множество в этом графе. Если существует несколько таких множеств, достаточно найти одно.
  • В задаче о независимом множестве максимального веса, входом служит неориентированный граф с весами, заданными для вершин, а выходом – независимое множество с максимальным общим весом. Задача о максимальном независимом множестве является частным случаем этой задачи с весами, равными единице.
  • В задаче перечисления наибольших независимых множеств входом служит неориентированный граф, а выходом – список всех наибольших независимых множеств. Задачу о максимальном независимом множестве можно решать как подзадачу данной задачи, поскольку максимальное независимое множество является наибольшим, и должно попасть в список.
  • В задаче о наличии независимого входом служит неориентированный граф и число k, а выходом – Да/Нет: Да, если граф содержит независимое множество размера k и Нет в противном случае.

Первые три задачи важны в практических приложениях, последняя же важна для теории NP-полноты для задач, связанных с независимыми множествами.

Задача о независимом множестве и задача о клике являются двойственными – клика в G – это независимое множество в дополнении графа G и наоборот. Таким образом, многие вычислительные результаты могут быть приложены одинаково хорошо к обоим задачам. Например, результаты, связанные с задачей о клике, имеют следующие следствия:

  • Задача о наличии является NP-полной, а потому не верится, что существует эффективный алгоритм её решения.
  • Задача о наибольшем максимальном множестве NP-трудна и её, кроме того, трудно аппроксимировать.

Нахождение максимальных независимых множеств[править | править вики-текст]

Задачу нахождение максимальных независимых множеств иногда называют "упаковкой вершин". Задача нахождения максимального независимого множества и задача о максимальной клике полиномиально эквивалентны – можно найти максимальное независимое множество путём поиска максимальной клики в дополнении графа, так что многие авторы особенно не заботятся о разделении этих двух задач. Обе задачи NP-полны, так что вряд ли их можно решить за полиномиальное время. Тем не менее, задача о максимальном множестве может быть решена эффективнее, чем за время O(n2 2n), которое даёт полный перебор, проверяющий все подмножества вершин, является ли он независимым множеством. Алгоритм Робсона [5] решает задачу за время O(20.276n) используя экспоненциальное пространство. Если есть ограничение на размер (полиномиальность пространства), существует алгоритм решения за время O*(1.2127n) .[6]

Вопреки близкой связи между максимальной кликой и максимальным независимом множестве в произвольном графе, задачи нахождения независимого множества и клики могут существенно отличаться, когда решаются на специальном классе графов. Например, для разреженных графов (графы, в которых в любом подграфе число рёбер не больше числа вершин, умноженного на некоторую константу), максимальная клика имеет ограниченный размер и может быть найдена точно за линейное время [7]. Тем не менее, для тех же классов графов, или даже для более жёстких ограничений у класса графов с ограниченной степенью, поиск максимального независимого множества является MAXSNP-полной[en], что означает, что для некоторой константы c (зависящей от степени) NP-трудно найти приближённое решение, отличающееся на множитель c от оптимального.[8] Однако эффективные приближённые алгоритмы известны, но для них гарантированная эффективность хуже, чем этот порог. Например, жадный алгоритм создаёт наибольшее независимое множество на каждом шаге выбирая вершину с минимальной степенью и удаляя её соседей. Этот алгоритм достигает гарантированной эффективности (Δ+2)/3 на графах с максимальной степенью  Δ.[9]

В некоторых классах графов, включая графы без клешней и совершенные графы (этомк классу принадлежат и деревья), максимальное независимое множество может быть найдено за полиномиальное время[10] Для планарных графов задача о максимальном независимом множестве остаётся NP-полной для точного решения, но может быть аппроксимирована с любой гарантированной эффективностью c < 1 за полиномиальное время. Похожие приближенные схемы полиномиального времени существуют в любом семействе минорно замкнутых[en] графов .[11][12]

В двудольных графах все вершины, не входящие в минимальное вершинное покрытие, могут быть включены в максимальное независимое множество (смотри теорему Кёнига). Поэтому минимальное вершинное покрытие может быть найдено с помощью алгоритма нахождения паросочетаний в двудольных графах.

Поиск наибольших независимых множеств[править | править вики-текст]

Задача поиска наибольших независимых множеств может быть решена за полиномиальное время простым жадным алгоритмом.[13] Все наибольшие независимые множества можно найти за время O(3n/3).

Программное обеспечение для поиска независимых множеств[править | править вики-текст]

Название Лицензия Язык API Описание
igraph GPL C, Python, R, Ruby точное решение
NetworkX BSD Python приближённое решение, см. процедуру maximum_independent_set
OpenOpt BSD Python точные и приближённые решения, возможность указать вершины, которые следует включить / исключить. См. класс STAB для деталей и примеров


Максимальное независимое множество в дереве[править | править вики-текст]

Если данный граф является деревом, то задача о независимом множестве эффективно решается методом динамического программирования.

Оптимальная подструктура задачи[править | править вики-текст]

Структура дерева сама подсказывает решение задачи: Обозначим корнем дерева любую вершину и назовем её r. Пусть I(u) обозначает размер максимального независимого множества вершин поддерева, корнем которого является вершина u. Тогда ответом на задачу будет являться I(r).

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

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 хранится 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|).

Литература[править | править вики-текст]

  • Richard Karp (1972). «Reducibility Among Combinatorial Problems». Proceedings of a Symposium on the Complexity of Computer Computations.
  • Michael R. Garey, David S. Johnson Computers and Intractability: A Guide to the Theory of NP-Completeness. — W.H. Freeman, 1979. — ISBN ISBN 0-7167-1045-5 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. — ISBN 0073523402
  • Najiba Sbihi Algorithme de recherche d'un stable de cardinalité maximum dans un graphe sans étoile (фр.) // Discrete Mathematics. — 1980. — В. 1. — Т. 29. — С. 53–76. — DOI:10.1016/0012-365X(90)90287-R.
  • M. Grötschel, L. Lovász, A. Schrijver Geometric Algorithms and Combinatorial Optimization. — Springer–Verlag, 1988. — Т. 2. — С. 296–298. — ISBN 0-387-13624-X.

См. также[править | править вики-текст]

Ссылки[править | править вики-текст]

  1. Chris Godsil, Gordon Royle Algebraic Graph Theory. — New York: Springer, 2001. — С. 3. — ISBN 0-387-95220-9
  2. В.А. Евстигнеев, В.Н. Касьянов Словарь по графам в информатике. — Новосибирск. — (Конструирование и оптимизация программ). — ISBN 978-591124-036-3
  3. J. W. Moon, Leo Moser On cliques in graphs // Israel Journal of Mathematics. — 1965. — В. 1. — Т. 3. — С. 23–28. — DOI:10.1007/BF02760024
  4. Zoltán Füredi The number of maximal independent sets in connected graphs // Journal of Graph Theory. — 1987. — В. 4. — Т. 11. — С. 463–470. — DOI:10.1002/jgt.3190110403
  5. J. M. Robson Algorithms for maximum independent sets // Journal of Algorithms. — 1986. — В. 3. — Т. 7. — С. 425–440. — DOI:10.1016/0196-6774(86)90032-5
  6. *Nicolas Bourgeois, Bruno Escoffier, Vangelis Th. Paschos, Johan M. M. van Rooij Algorithm theory—SWAT 2010. — Berlin: Springer, 2010. — Т. 6139. — С. 62–73. — (Lecture Notes in Computer Science). — DOI:10.1007/978-3-642-13731-0_7.
  7. N. Chiba, T. Nishizeki Arboricity and subgraph listing algorithms // SIAM Journal on Computing. — 1985. — В. 1. — Т. 14. — С. 210–223. — DOI:10.1137/0214017
  8. Piotr Berman, Toshihiro Fujito {{{заглавие}}}. — 1995. — Т. 955. — С. 449–460. — (Lecture Notes in Computer Science). — DOI:10.1007/3-540-60220-8_84.
  9. M. M. Halldórsson, J. Radhakrishnan Greed is good: Approximating independent sets in sparse and bounded-degree graphs // Algorithmica. — 1997. — В. 1. — Т. 18. — С. 145–163. — DOI:10.1007/BF02523693.
  10. Для графов без клешней смотрите Sbihi, 1980. Для совершенных графов смотрите M. Grötschel, L. Lovász, A. Schrijver, 1988.
  11. Brenda S. Baker Approximation algorithms for NP-complete problems on planar graphs // Journal of the ACM. — 1994. — В. 1. — Т. 41. — С. 153–180. — DOI:10.1145/174644.174650
  12. Martin Grohe Local tree-width, excluded minors, and approximation algorithms // Combinatorica. — 2003. — В. 4. — Т. 23. — С. 613–632. — DOI:10.1007/s00493-003-0037-9
  13. Michael Luby A simple parallel algorithm for the maximal independent set problem // SIAM Journal on Computing. — 1986. — В. 4. — Т. 15. — С. 1036–1053. — DOI:10.1137/0215074.