Jak szybko możemy obliczyć zbiór poetów w zestawie rodziny zestawów?

Biorąc pod uwagę określoną rodzinę podzbiorów uniwersum . Niech a my chcemy odpowiedzieć to . $\mathcal{F}$ $U$ $S_1,S_2 \in \mathcal F$ $S_1 \subseteq S_2$

Szukam struktury danych, która pozwoli mi szybko odpowiedzieć na to pytanie. Moja aplikacja pochodzi z teorii grafów, w której chcę sprawdzić, czy usunięcie wierzchołka i jego sąsiedztwa pozostawia izolowane wierzchołki, a dla każdej listy wierzchołków pozostawia wszystkie izolowane wierzchołki.

Chcę utworzyć kompletny zestaw pojęć lub ostatecznie tabelę przechowującą prawdziwe fałszywe powiedzenie, które zestawy są wzajemnie podzbiórami. $|\mathcal{F}|^2$

Niech,i, zakładamy, $m = \sum_{S\in \mathcal{F}} |S|$ $u = |U|$ $n = |\mathcal{F}|$ $u,n \leq m$

Możemy wygenerować macierz (dwuczęściowy) w czasie a następnie stworzyć tabelę wszystkich porównań w czasie dla każdego zestawu , pętli wszystkich składników innych pakietów i oznaczyć jako zestaw nie podzbiór wtedy, gdy element nie jest w . Całkowity czas . $n \times u$ $O(un)$ $n^2$ $O(nm)$ $S \in \mathcal{F}$ $S$ $S$ $O(nm)$

Czy możemy zrobić coś szybciej? W szczególności, czy czas możliwy, czy nie? $O((n+u)^2)$

Znalazłem kilka powiązanych artykułów:

Prosty algorytm subkwadratowy do obliczania podzbioru częściowej kolejności (1995), który daje algorytm . $O(m^2 / log(m))$

Podzbiór częściowej kolejności: Obliczenia i kombinatoryka nieznacznie poprawia powyższe, ale również twierdzi, że powyższy artykuł rozwiązuje problem w czasie gdzie jest maksymalną liczbą zbiorów dzielących wspólny element, ale nie mogłem zrozumieć tego wyniku. $O(md)$ $d$

W artykule Pomiędzy i $O(nm)$ $O(n^{\alpha})$ autorzy pokazują, jak na wykresie znaleźć połączone komponenty po usunięciu zamkniętego sąsiedztwa wierzchołka za pomocą mnożenia macierzy. Można tego użyć do obliczenia zestawu punktów włączenia przez znalezienie wszystkich składników, które są singletonami, w środowisku wykonawczym . $O((n+u)^{2.79})$

Powiązana jest także ta dyskusja na forum: Jaki jest najszybszy sposób sprawdzenia włączenia zestawu? co implikuje dolną granicę . $O(n^{2-\epsilon})$

graph-algorithms ds.data-structures partial-order

— Martin Vatshelle
źródło

Tylko sugestia: czy możesz uprościć pytanie, ustawiając ? Czy oba parametry są ważne w twojej aplikacji?

u = n

$u=n$

— Colin McQuillan

W mojej aplikacji mam gdzie oznacza asymptotycznie mniejsze.

u << n << 2^{u}

$u << n << 2^u$

<<

$<<$

— Martin Vatshelle

Jeśli losowość jest w granicach, jednym z grubszych pomysłów byłoby wygenerowanie szeregu funkcji „losowej sygnatury monotonicznej” i wykorzystanie ich do przybliżenia relacji podzbioru (filtry la Blooma). Niestety nie wiem, jak zrobić z tego praktyczny algorytm, ale oto kilka szacunków, które nie od razu dowodzą, że pomysł jest niemożliwy. Jest to bardzo dalekie od użytecznego rozwiązania, ale napiszę to na wypadek, gdyby to pomogło.

Załóżmy dla uproszczenia, że wszystkie zestawy są prawie tego samego rozmiaru, powiedzmy , a to . Możemy założyć , w przeciwnym razie skończymy. Zdefiniuj Pamiętaj, że . $|S| = s \pm O(1)$ $s = o(u)$ $1 \ll s$

\begin{aligned} q & = [s / 2] \\ p & = [\frac{(\binom{u}{q})}{(\binom{s}{q})}] \end{aligned}

$\begin{aligned} q &= [s/2] \\ p &= \left[\frac{u \choose q}{s \choose q}\right] \end{aligned}$

p ≫ 1

$p \gg 1$

Oto bardzo niepraktyczna część. Losowo wybierz podzestawy z zamiennikiem, każdy o rozmiarze , i zdefiniuj funkcję przez iff dla niektórych . Przy stałej i zmieniających się losowo, mamy Ponieważ jest monotoniczny, implikacja $p$ $A_1, \ldots, A_p \subset U$ $q$ $f : 2^U \to \{0,1\}$ $f(S) = 1$ $A_i \subset S$ $i$ $S$ $A_i,f$

\begin{aligned} Pr (f (S) = 0) & = Pr (\forall i . A_{i} ⊄ S) \\ = Pr (A_{1} ⊄ S)^{p} \\ = {(1 - (\binom{s}{q}) / (\binom{u}{q}))}^{p} \\ = e^{- Θ (1)} \end{aligned}

$\begin{aligned} \Pr(f(S) = 0) &= \Pr(\forall i. A_i \not\subset S) \\ &= \Pr(A_1 \not\subset S)^p \\ &= \left(1 - {s \choose q}/{u \choose q}\right)^p \\ &= e^{-\Theta(1)} \end{aligned}$

f (S)

$f(S)$

S \subset T

$S \subset T$

f (S) \leq f (T)

$f(S) \le f(T)$ . Jeśli , napraw niektóre . Prawdopodobieństwo, że wykryje to

T ⊄ S

$T \not\subset S$

t \in T - S

$t \in T-S$

f

$f$

T ⊄ S

$T \not\subset S$

\begin{aligned} Pr (f (S) = 0 < 1 = f (T)) & = Pr (f (S) = 0) Pr (f (T) = 1 | f (S) = 0) \\ = e^{- Θ (1)} Pr (\exists i . A_{i} \subset T, A_{i} \cap T - S \neq 0 | f (S) = 0) \\ = e^{- Θ (1)} Pr (\exists i . t \in A_{i} \subset T | f (S) = 0) \\ \leq e^{- Θ (1)} Pr (\exists i . t \in A_{i} \subset T) \\ \approx e^{- Θ (1)} p Pr (t \in A_{1} \subset T) \\ \leq e^{- Θ (1)} p (\binom{s}{q - 1}) / (\binom{u}{q}) \\ \approx e^{- Θ (1)} p \frac{q}{s - q} (\binom{s}{q}) / (\binom{u}{q}) \\ = e^{- Θ (1)} \end{aligned}

$\begin{aligned} \Pr(f(S) = 0 < 1 = f(T)) &= \Pr(f(S) = 0) \Pr(f(T) = 1 | f(S) = 0) \\ &= e^{-\Theta(1)} \Pr(\exists i. A_i \subset T, A_i \cap T-S \ne 0 | f(S) = 0) \\ &= e^{-\Theta(1)} \Pr(\exists i. t \in A_i \subset T | f(S) = 0) \\ &\le e^{-\Theta(1)} \Pr(\exists i. t \in A_i \subset T) \\ &\approx e^{-\Theta(1)} p \Pr(t \in A_1 \subset T) \\ &\le e^{-\Theta(1)} p {s \choose q-1} / {u \choose q} \\ &\approx e^{-\Theta(1)} p \frac{q}{s-q} {s \choose q} / {u \choose q} \\ &= e^{-\Theta(1)} \end{aligned}$ Niektóre z tych kroków są dość wątłe, ale nie mam czasu, aby je dziś poprawić. W każdym razie, jeśli wszystkie one zachowują, to przynajmniej nie jest wyraźnie niemożliwe losowe wygenerowanie funkcji podpisu, które mają rozsądne prawdopodobieństwo odróżnienia podzbiorów od nieoznaczonych. Logarytmiczna liczba takich funkcji prawidłowo rozróżniałaby wszystkie pary. Jeśli wygenerowanie funkcji podpisu i obliczenie można zredukować do czasu , wynikiem byłby ogólny algorytm .

f

$f$

f (S)

$f(S)$

\tilde{O} (n + u)

$\tilde{O}(n+u)$

\tilde{O} (n^{2} + u^{2})

$\tilde{O}(n^2+u^2)$

Nawet jeśli powyższe obliczenia są prawidłowe, nie mam pojęcia, jak szybko wygenerować monotoniczne funkcje podpisu o pożądanych cechach. Jest również prawdopodobne, że ta technika nie rozciąga się na znacząco różne rozmiary zestawu.

— Geoffrey Irving
źródło