Некоторые алгоритмы для поиска независимых множеств в двудольных графах:

• Алгоритм нахождения наибольшего паросочетания в двудольных графах. 14 Согласно теореме Кёнига, в двудольных графах все вершины, не входящие в наименьшее вершинное покрытие, могут быть включены в наибольшее независимое множество. 14
• Рекурсивный алгоритм построения независимых множеств для подграфов. 5 Он работает следующим образом: 5

1. Берут произвольную вершину графа G. 5
2. Стирают из графа её саму и всех её соседей. 5 Получается подграф G'. 5
3. Для G' находят множество независимых множеств. 5
4. В каждое из независимых множеств G' добавляют вершину v. 5
5. Повторяют алгоритм для всех остальных вершин G. 5

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