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

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 и продолжать оттуда, хотя я не уверен, насколько это изменится.

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