Алгоритм максимального независимого набора

Question

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

Я задаюсь вопросом о псевдокоде, чтобы найти все возможные множества вершин.

Скажем, дан двудольный граф с 4 синими вершинами и 4 красными. В настоящее время я бы

Start with an arbitrary blue,
  find all red that don't match this blue
  put all these red in Independent Set
  find all blue that dont match these red
  put these blue in Independent Set
  Repeat for next vertex in blue

Repeat all over again for all blue then all vertices in red.

Я понимаю, что этот способ вообще не дает мне всех возможных комбинаций независимых наборов, поскольку после первого шага я выбираю все следующие цветовые вершины, которые не совпадают, а не перебираю все возможности.

Например, дан график с совпадающим

B  R
1  1
1  3 
2  1
2  3
3  1
3  3
4  2
4  4

Start with blue 1
  Choose red 2 and 4 since they dont match
  Add 2, 4 to independent Set
  Choose 2 and 3 from blue since they dont with 2 or 4 from red
  Add 2 and 3 from blue to independent set as well.
Independent Set = 1,2,3 from blue 2,4 from red
Repeat for blue 2, blue 3, ... red n (storing the cardinality for each set)

Есть ли способ, как я могу улучшить этот алгоритм, чтобы лучше искать все возможности. Я знаю, что | Максимальный набор для двудольного графа | = | Красный | + | Синий | - | Максимальное соответствие |.

Проблема возникает с возможностью того, что при выборе всех возможных красных в первом случае для данного синего цвета, если эти красные соединяются со всеми другими возможными синими, тогда в моем сете всегда есть только 1 синий и остальной красный.

Answer 1

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

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

Answer 2

Как упоминает Аарон МакДейд в своем теперь удаленном ответе, проблема поиска максимального независимого набора эквивалентна поиску максимальной клики. Эквивалентность заключается в том, что нахождение максимального независимого множества в графе G аналогично нахождению максимальной клики в дополнении G. Задача, как известно, является NP-полной.

Решение о грубой силе, о котором вы упоминаете, занимает O(n^2 2^n), но вы можете добиться большего, чем это. У Робсона есть статья под названием «Алгоритмы для максимально независимых наборов» 1986 года, в которой приводится алгоритм, который принимает O(2^{c*n}) для константы 0<c<1 (я считаю, c составляет около 1/4, но я могу ошибаться). это характерно для двудольного графа.

Стоит отметить, что если у вас двудольный граф, любая из сторон образует независимое множество. В полном двудольном графе K_{b,r}, который разделен B x R на |B|=b и |R|=r, где есть ребро от каждой вершины в B до каждой вершины в R и ни одного в B, ни одного в пределах R, максимальный независимый набор равен B, если b>=r, в противном случае это R.

Взятие B или R вообще не сработает. sdcvvc отметил пример с вершинами {1,2,3,A,B,C} и ребрами {A,1}, {A,2}, {A,3}, {B,3}, {C,3}. В этом случае максимальный независимый набор равен {1,2,B,C}, что больше, чем раздел {A,B,C} или {1,2,3}.

.

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

В качестве альтернативы вы можете использовать алгоритм Хопкрофта-Карпа на двудольном дополнении графа, чтобы найти максимальное совпадение, а затем взять вершины, используемые в сопоставлении, в качестве независимого набора. Это дает алгоритм полиномиального времени для решения проблемы.