Cálculo del cierre del sindicato

Dada una familia de a lo sumo n subconjuntos de { 1 , 2 , ... , n } . El cierre unión F es otra familia conjunto C que contiene cada conjunto que puede ser construido mediante la adopción de la unión de 1 o más conjuntos en F . Por | C | denotamos el número de juegos en C .$\mathcal F$$n$$\{ 1, 2, \dots, n \}$$\mathcal F$$\mathcal C$$\mathcal F$$|\mathcal C|$$\mathcal C$

¿Cuál es la forma más rápida de calcular el cierre de la unión?

He mostrado una equivalencia entre el cierre de la unión y la lista de todos los conjuntos independientes máximos en un gráfico bipartito, por lo tanto, sabemos que decidir el tamaño del cierre de la unión es # P-completo.

Sin embargo, hay una manera de enumerar todos los conjuntos independientes máximos (o camarillas máximas) en el tiempo para un gráfico con n nodos y m bordes Tsukiyama et al. 1977. Pero esto no está especializado para gráficos bipartitos.$O(|\mathcal C| \cdot nm)$$n$$m$

Dimos un algoritmo para gráficos bipartitos con tiempo de ejecución http://www.ii.uib.no/~martinv/Papers/BooleanWidth_I.pdf$|\mathcal C| \cdot \log |\mathcal C| \cdot n^2$

Nuestro método se basa en la observación de que cualquier elemento en puede hacerse mediante la unión de algún otro elemento de C y uno de los conjuntos originales. Por lo tanto, cada vez que agreguemos un elemento a C, intentaremos expandirlo en uno de los n conjuntos originales. Para cada uno de estos n ⋅ | C | Establece que necesitamos para comprobar si todavía están en C . Almacenamos C como un árbol de búsqueda binario, por lo que cada búsqueda toma log | C | ⋅ n tiempo.$C$$C$$C$$n$$n \cdot |C|$$C$$C$$\log |C| \cdot n$

¿Es posible encontrar el cierre de la unión en el tiempo O ( | C | ⋅ n 2 ) ? ¿O incluso a tiempo O ( | C | ⋅ n ) ?$\mathcal C$$O(|\mathcal C| \cdot n^2)$$O(|\mathcal C| \cdot n)$

La complejidad de enumerar conjuntos independientes máximos en gráficos es la misma que en los gráficos bipartitos, por lo que la bipartididad no aporta nada nuevo.

$O(|C|\cdot n^2)$