À quelle vitesse pouvons-nous calculer le poset d'inclusion d'ensemble d'une famille d'ensemble?

Compte tenu d' une famille ensemble $\mathcal{F}$ de sous - ensembles d'un univers $U$ . Soit $S_1,S_2 \in \mathcal F$ et nous voulons répondre est $S_1 \subseteq S_2$ .

Je recherche une structure de données qui me permettra d'y répondre rapidement. Mon application est de la théorie des graphes où je veux voir si la suppression d'un sommet et de son voisinage laisse des sommets isolés, et pour chaque sommet liste tous les sommets isolés qu'il laisse.

Je veux créer le poset complet ou éventuellement un $|\mathcal{F}|^2$ tableaux stockant de vrais faux indiquant exactement quels ensembles sont des sous-ensembles les uns des autres.

Soit $m = \sum_{S\in \mathcal{F}} |S|$, $u = |U|$et $n = |\mathcal{F}|$, supposons $u,n \leq m$

Nous pouvons générer la matrice de confinement $n \times u$ (le graphique bipartite) en temps $O(un)$ puis créer le tableau de toutes les $n^2$ comparaisons en temps $O(nm)$ par pour chaque ensemble $S \in \mathcal{F}$ , parcourir tous les éléments de tous les autres ensembles et marquer le jeu en tant que pas un sous - ensemble de $S$ si l'élément se trouve pas dans $S$ . Temps total $O(nm)$ .

Pouvons-nous faire quelque chose plus rapidement? En particulier, le temps $O((n+u)^2)$ -il possible ou non?

J'ai trouvé quelques articles liés:

Un algorithme sub-quadratique simple pour calculer l'ordre partiel de sous-ensemble (1995) qui donne un algorithme $O(m^2 / log(m))$ .

L'ordre partiel du sous-ensemble: informatique et combinatoire améliore légèrement ce qui précède, mais affirme également que l'article ci-dessus résout le problème en temps $O(md)$ où $d$ est le nombre maximal d'ensembles partageant un élément commun, mais je ne pouvais pas comprendre ce résultat.

Dans l'article Entre et O ( n α$O(nm)$$O(n^{\alpha})$ les auteurs montrent comment dans un graphique trouver les composants connectés après avoir supprimé le voisinage fermé d'un sommet en utilisant la multiplication matricielle. Ceci peut être utilisé pour calculer le poset d'inclusion défini en trouvant tous les composants qui sont des singletons avec un temps d'exécution de .$O((n+u)^{2.79})$

Cette discussion sur le forum est également liée: Quel est le moyen le plus rapide de vérifier l'inclusion d'un ensemble? ce qui implique une borne inférieure de .$O(n^{2-\epsilon})$

Si le caractère aléatoire est dans les limites, une idée approximative serait de générer un tas de fonctions de "signature monotone aléatoire" et de les utiliser pour approximer la relation de sous-ensemble (à la filtre de Bloom). Malheureusement, je ne sais pas comment en faire un algorithme pratique, mais voici quelques estimations qui ne prouvent pas immédiatement que l'idée est impossible. C'est très loin d'une solution utile, mais je l'écrirai au cas où cela aiderait.

Supposons pour plus de simplicité que les ensembles sont presque tous de la même taille, par exemple , et que s = o ( u ) . Nous pouvons supposer 1 ≪ s , sinon nous avons terminé. Définir $|S| = s \pm O(1)$$s = o(u)$$1 \ll s$ Notez quep≫1.

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

Voici la partie extrêmement impraticable. Choisir aléatoirement sous-ensembles A 1 , … , A p ⊂ U avec remplacement, chacun de taille q , et définir une fonction$p$$A_1, \ldots, A_p \subset U$$q$ par f ( S ) = 1 ssi A i ⊂ S pour certains i . Avec S fixe et A i , f variant aléatoirement, nous avons $f : 2^U \to \{0,1\}$$f(S) = 1$$A_i \subset S$$i$$S$$A_i,f$ Puisquef(S)est monotone,S⊂Timpliquef(S)≤f

$$\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$ . Si T ⊄ S , fixercertain t ∈ T - S . La probabilité que f détecte T ⊄ S est Pr ( f ( S ) = 0 < 1 = $f(S) \le f(T)$$T \not\subset S$$t \in T-S$$f$$T \not\subset S$ Certaines de ces étapes sont assez ténues, mais je n'ai pas le temps de les améliorer ce soir. Dans tous les cas, s'ils le sont tous, alors au moins il n'est pas clairement impossible de générer de manière aléatoire des fonctions de signature qui ont une probabilité raisonnable de distinguer les sous-ensembles des non-sous-ensembles. Un nombre logarithmique de ces fonctions distinguerait alors correctement toutes les paires. Si la génération d'une fonction de signaturefet le calcul def(S)pouvaient être réduits à un temps ˜ O (n+u), le résultat serait 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)$ algorithme.$\tilde{O}(n^2+u^2)$

Même si les calculs ci-dessus sont corrects, je ne sais pas comment générer rapidement des fonctions de signature monotone avec les fonctionnalités souhaitées. Il est également probable que cette technique ne s'étende pas à des tailles de jeu sensiblement différentes.