Obliczanie zamknięcia związku

Biorąc pod uwagę rodzinę najwyżej podzbiorów . Zamknięcie związek jest inny zestaw rodziny zawierający każdy zestaw, które mogą być skonstruowane poprzez związek 1 lub więcej grup w . Przez oznaczymy liczbę zestawów w . $\mathcal F$ $n$ $\{ 1, 2, \dots, n \}$ $\mathcal F$ $\mathcal C$ $\mathcal F$ $|\mathcal C|$ $\mathcal C$

Jaki jest najszybszy sposób na obliczenie zamknięcia związku?

Wykazałem równoważność między zamknięciem unii a listowaniem wszystkich maksymalnych niezależnych zbiorów na grafie dwustronnym, dlatego wiemy, że decyzja o wielkości zamknięcia unii jest # P-ukończona.

Jednak nie jest to sposób wymienić wszystkie maksymalne niezależne zestawy (lub maksymalne klik) w czas na wykresie węzłów i krawędzie Tsukiyama i inni. 1977. Nie jest to jednak wyspecjalizowane w przypadku grafów dwustronnych. $O(|\mathcal C| \cdot nm)$ $n$ $m$

Daliśmy algorytm dla grafów dwustronnych z runtime http://www.ii.uib.no/~martinv/Papers/BooleanWidth_I.pdf $|\mathcal C| \cdot \log |\mathcal C| \cdot n^2$

Nasza metoda opiera się na obserwacji, że dowolny element w może być wykonany przez połączenie jakiegoś innego elementu i jednego z oryginalnych zbiorów. Dlatego za każdym razem, gdy dodamy element do spróbujemy rozszerzyć go o jeden z oryginalnych zestawów. Dla każdego z tych ustawia musimy sprawdzić, czy są one nadal w . Przechowujemy jako drzewo wyszukiwania binarnego, więc każde wyszukiwanie zajmuje razem. $C$ $C$ $C$ $n$ $n \cdot |C|$ $C$ $C$ $\log |C| \cdot n$

Czy można znaleźć związek zamknięcia w czasie ? Czy nawet w czasie ? $\mathcal C$ $O(|\mathcal C| \cdot n^2)$ $O(|\mathcal C| \cdot n)$

— Martin Vatshelle
źródło

W równoważności, którą wykazałeś między zamknięciem związku a maksymalnym ind. zestawów na wykresach dwustronnych, czy równoważność jest bijection? Lub innymi słowy, w twoim algorytmie do wyliczenia wszystkich indeksu mieszanego. zestawy wykresu dwustronnego, to

liczba maksymalnych ind. zestawy?

| C |

$|C|$

— Vinayak Pathak,

Tak, to bijection, więc

to liczba maksymalnych niezależnych zestawów. (zwróć uwagę, że pusty zestaw musi być zdefiniowany jako

| C |

$|C|$

C

$C$

— Martin Vatshelle,

Chociaż jest mało prawdopodobne, aby to pomogło w twoim pytaniu, to, co zadajesz, jest szczególnym przypadkiem obliczenia górnego zamknięcia elementów w sieci i zastanawiam się, czy są tam wyniki, które mogą być przydatne.

— Suresh Venkat

Ankieta, na którą wskazuję w mojej odpowiedzi poniżej, zawiera pewne linki do sieci.

— M. kanté

Złożoność wyliczania maksymalnych niezależnych zbiorów na wykresach jest taka sama jak na grafach dwustronnych, więc dwustronność nie przynosi niczego nowego.

$O(|C|\cdot n^2)$

— M. kanté
źródło