¿Qué tan rápido podemos calcular el conjunto de inclusión de una familia de conjuntos?

Dada una familia conjunto $\mathcal{F}$ de subconjuntos de un universo $U$ . Deje $S_1,S_2 \in \mathcal F$ y queremos responder es $S_1 \subseteq S_2$ .

Estoy buscando una estructura de datos que me permita responder rápidamente a esto. Mi aplicación es de la teoría de grafos donde quiero ver si eliminar un vértice y su vecindario deja vértices aislados, y para cada vértice enumera todos los vértices aislados que deja.

Quiero crear el poset completo o eventualmente un $|\mathcal{F}|^2$ tablas que almacenan verdadero falso decir exactamente qué conjuntos están subconjuntos entre sí.

Sea $m = \sum_{S\in \mathcal{F}} |S|$, $u = |U|$y $n = |\mathcal{F}|$, supongamos que $u,n \leq m$

Podemos generar la matriz de contención $n \times u$ (el gráfico bipartito) en tiempo $O(un)$ y luego podemos crear la tabla de todas las comparaciones $n^2$ en tiempo $O(nm)$ por cada conjunto $S \in \mathcal{F}$ , recorrer todo elementos de todos los otros conjuntos y marcan el conjunto como no un subconjunto de $S$ si el elemento no se encuentra en $S$ . En total $O(nm)$ tiempo.

¿Podemos hacer algo más rápido? En particular, ¿es posible $O((n+u)^2)$ tiempo o no?

Encontré algunos artículos relacionados:

Algoritmo subcuadrático simple para calcular el orden parcial del subconjunto (1995) que proporciona un algoritmo $O(m^2 / log(m))$ .

El orden parcial del subconjunto: computación y combinación mejora ligeramente lo anterior, pero también afirma que el documento anterior resuelve el problema en el tiempo donde d es el número máximo de conjuntos que comparten un elemento común, pero no pude entender este resultado.$O(md)$$d$

En el artículo Entre y O ( n α$O(nm)$$O(n^{\alpha})$ los autores muestran cómo en un gráfico encontrar los componentes conectados después de eliminar la vecindad cerrada de un vértice utilizando la multiplicación de matrices. Esto se puede utilizar para calcular el conjunto de inclusión del conjunto al encontrar todos los componentes que son singletons con un tiempo de ejecución de .$O((n+u)^{2.79})$

También esta discusión del foro está relacionada: ¿Cuál es la forma más rápida de verificar la inclusión de conjuntos? lo que implica un límite inferior de .$O(n^{2-\epsilon})$

Si la aleatoriedad está dentro de los límites, una idea aproximada sería generar un grupo de funciones de "firma monotónica aleatoria" y usarlas para aproximar la relación del subconjunto (a la Bloom filtros). Desafortunadamente, no sé cómo convertir esto en un algoritmo práctico, pero aquí hay algunas estimaciones que no prueban de inmediato que la idea sea imposible. Esto está muy lejos de ser una solución útil, pero lo escribiré en caso de que ayude.

Supongamos por simplicidad que los conjuntos son casi del mismo tamaño, digamos , y que s = o ( u ) . Podemos suponer 1 ≪ s , de lo contrario, hemos terminado. Definir $|S| = s \pm O(1)$$s = o(u)$$1 \ll s$ Tenga en cuenta quep≫1.

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

Aquí está la parte muy poco práctica. Elija aleatoriamente subconjuntos A 1 , ... , A p ⊂ U con reemplazo, cada uno de tamaño q , y defina una función f : 2 U → { 0 , 1 } por f ( S ) = 1 iff A i ⊂ S para alguna i . Con S fijo y A i , f variando aleatoriamente, tenemos $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$ Dado quef(S)es monótono,S⊂Timplicaf(S)≤f(T). SiT⊄S, solucionar algunost∈T-S. La probabilidad de quefdetecteT⊄Ses Pr ( f ( S ) = 0 < 1 =

$$\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)$$S \subset T$$f(S) \le f(T)$$T \not\subset S$$t \in T-S$$f$$T \not\subset S$ Algunos de esos pasos son bastante tenues, pero no tengo tiempo para mejorarlos esta noche. En cualquier caso, si todos se mantienen, entonces al menos no es claramente imposible generar aleatoriamente funciones de firma que tengan una probabilidad razonable de distinguir los subconjuntos de los no subconjuntos. Un número logarítmico de tales funciones distinguiría todos los pares correctamente. Si la generación de una función de firmafy el cálculo def(S)pudieran reducirse a ˜ O (n+u)tiempo, el resultado sería un ˜ O global(n $$\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}$$ $f$$f(S)$$\tilde{O}(n+u)$ algoritmo.$\tilde{O}(n^2+u^2)$

Incluso si los cálculos anteriores son correctos, no tengo idea de cómo generar funciones de firma monótonas con las características deseadas rápidamente. También es probable que esta técnica no se extienda a tamaños de conjuntos significativamente diferentes.