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

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

Меня интересует псевдокод для поиска всех возможных наборов вершин.

Скажем, дан двудольный граф с 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)

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

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