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

Question

Это двудольный граф, и мы хотим перечислить все максимальные полные двудольные подграфы.

Например,

множество вершин L = {A, B, C, D}

множество вершин R = {а, б, в, д, е}

края: Aa , Ab, Ba, Bb, Cc, Cd, Dc, Dd, Де

максимальный полный двудольный являются:

{A, B} - {а, Ь}

{C, D} - {C, D}

{D} - {C, D, E}

Я нашел алгоритм грубой силы, O (2^п). Я не знаю, есть ли какой-то алгоритм аппроксимации или рандомизированный алгоритм.

Answer 1

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

Алгоритм Брон-Кербоша можно использовать для перечисления всех максимальных клик в графе (не обязательно двудольных). Его довольно легко реализовать и имеет немного лучшую худшую временную привязку O (3^(n/3)). Существует также фиксированный параметр сжимаемой временной привязкой в ​​терминах вырождения графа.