Calcul de la fermeture du syndicat

Étant donné une famille d'au plus sous-ensembles de . La fermeture de l' union \ mathcal F est un autre ensemble famille \ mathcal C contenant tout ensemble qui peut être construit en prenant l'union de 1 ou plusieurs ensembles de \ mathcal F . Par | \ mathcal C | on note le nombre de jeux dans \ mathcal C . n { 1 , 2 , … , n } F C F | C | $\mathcal F$$n$$\{ 1, 2, \dots, n \}$$\mathcal F$$\mathcal C$$\mathcal F$$|\mathcal C|$$\mathcal C$

Quel est le moyen le plus rapide pour calculer la fermeture d'un syndicat?

J'ai montré une équivalence entre la fermeture d'union et la liste de tous les ensembles indépendants maximaux dans un graphe bipartite, donc nous savons que décider de la taille de la fermeture d'union est # P-complet.

Cependant, il existe un moyen de lister tous les ensembles indépendants maximaux (ou cliques maximales) en temps $O(|\mathcal C| \cdot nm)$ pour un graphe à $n$ nœuds et $m$ bords Tsukiyama et al. 1977. Mais ce n'est pas spécialisé pour les graphes bipartis.

Nous avons donné un algorithme pour les graphes bipartis avec runtime $|\mathcal C| \cdot \log |\mathcal C| \cdot n^2$ http://www.ii.uib.no/~martinv/Papers/BooleanWidth_I.pdf

Notre méthode est basée sur l'observation que tout élément de $C$ peut être fait par l'union d'un autre élément de $C$ et d'un des ensembles originaux. Par conséquent, chaque fois que nous ajouterons un élément à $C$ essaierons de le développer par l'un des $n$ ensembles originaux. Pour chacun de ces $n \cdot |C|$ensembles nous devons vérifier si elles sont encore en $C$ . Nous stockons $C$ comme un arbre de recherche binaire, donc chaque recherche prend $\log |C| \cdot n$ time.

Est-il possible de trouver la fermeture d'union $\mathcal C$ en temps $O(|\mathcal C| \cdot n^2)$ ? Ou même dans le temps $O(|\mathcal C| \cdot n)$ ?

La complexité de l'énumération d'ensembles indépendants maximaux dans les graphiques est la même que dans les graphiques bipartites, donc la bipartité n'apporte rien de nouveau.

Vous avez un algorithme (avec un espace exponentiel) dans , mais aucun algorithme d'espace polynomial qui atteint cette complexité temporelle n'est connu. Le document suivant http://www.sciencedirect.com/science/article/pii/S0166218X08004563 est une bonne enquête.$O(|C|\cdot n^2)$