Obliczanie zamknięcia związku

Biorąc pod uwagę rodzinę najwyżej n podzbiorów { 1 , 2 , … , n } . Zamknięcie związek C jest inny zestaw rodziny C zawierający każdy zestaw, które mogą być skonstruowane poprzez związek 1 lub więcej grup w F . Przez | C | oznaczymy liczbę zestawów w C .$\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 n węzłów i m 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 C i jednego z oryginalnych zbiorów. Dlatego za każdym razem, gdy dodamy element do C, spróbujemy rozszerzyć go o jeden z n oryginalnych zestawów. Dla każdego z tych n ⋅ | C | ustawia musimy sprawdzić, czy są one nadal w C . Przechowujemy C jako drzewo wyszukiwania binarnego, więc każde wyszukiwanie zajmuje log | C | ⋅ n razem.$C$$C$$C$$n$$n \cdot |C|$$C$$C$$\log |C| \cdot n$

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

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)$