Для данного семейства не более подмножеств . Замыкание объединения другого набор семейство , содержащий каждый набор , который можно построить, взяв объединение 1 или более множеств в . Byмы обозначим число множеств в . n { 1 , 2 , … , n } F C F | C | С
Какой самый быстрый способ вычислить закрытие объединения?
Я показал эквивалентность между замыканием объединения и перечислением всех максимальных независимых множеств в двудольном графе, поэтому мы знаем, что определение размера замыкания объединения является # P-полным.
Однако есть способ перечислить все максимальные независимые множества (или максимальные клики) за времени для графа с узлами и ребрами Tsukiyama et al. 1977. Но это не специализировано для двудольных графов.n m
Мы дали алгоритм для двудольных графов со временем выполнения http://www.ii.uib.no/~martinv/Papers/BooleanWidth_I.pdf
Наш метод основан на наблюдении, что любой элемент в может быть сделан объединением некоторого другого элемента и одного из исходных наборов. Следовательно, всякий раз, когда мы добавляем элемент в пытаемся расширить его на один из исходных наборов. Для каждого из этихустанавливает нам нужно проверить , если они все еще находятся в . Мы храним как двоичное дерево поиска, поэтому каждый поиск занимает раз.C C n n ⋅ | C | C C log | C | ⋅ н
Можно ли найти объединение за времени? Или даже во времени ?
источник
Ответы:
Сложность перечисления максимальных независимых множеств в графах такая же, как и в двудольных графах, поэтому двудольность не приносит ничего нового.
источник