Computando o fechamento da união

10

Dada uma família de no máximo subconjuntos de . O fecho de união é uma outra família conjunto contendo cada conjunto que pode ser construído, tendo a união de 1 ou mais conjuntos em . Pordenotamos o número de conjuntos em . n { 1 , 2 , , n } F CFn{1,2,,n}FCF|C|C

Qual é a maneira mais rápida de calcular o fechamento da união?

Eu mostrei uma equivalência entre o fechamento da união e a lista de todos os conjuntos independentes máximos em um gráfico bipartido; portanto, sabemos que decidir o tamanho do fechamento da união é # P-completo.

No entanto, há uma forma de listar todos os conjuntos independentes máximas (ou cliques maximais) em tempo para um gráfico com nodos e arestas Tsukiyama et al. 1977. Mas isso não é especializado em gráficos bipartidos.O(|C|nm)nm

Demos um algoritmo para gráficos bipartidos com tempo de execução http://www.ii.uib.no/~martinv/Papers/BooleanWidth_I.pdf|C|log|C|n2

Nosso método é baseado na observação de que qualquer elemento em pode ser produzido pela união de algum outro elemento de C e um dos conjuntos originais. Portanto, sempre que adicionarmos um elemento a C, tentaremos expandi-lo por um dos n conjuntos originais. Para cada um desses n | C | define precisamos verificar se eles ainda estão em C . Armazenamos C como uma árvore de pesquisa binária, para que cada pesquisa faça log | C | n tempo.CCCnn|C|CClog|C|n

É possível encontrar o fechamento da união no tempo O ( | C |n 2 ) ? Ou mesmo a tempo O ( | C |n ) ?CO(|C|n2)O(|C|n)

Martin Vatshelle
fonte
|C|
|C|C
Embora seja improvável que isso ajude com sua pergunta, o que você está perguntando é um caso especial de calcular o fechamento ascendente de elementos em uma treliça, e me pergunto se há resultados a partir daí que possam ser úteis.
precisa
A pesquisa que aponto na minha resposta abaixo fornece alguns links com treliças.
kanté 13/11/12

Respostas:

3

A complexidade de enumerar conjuntos independentes máximos em gráficos é a mesma que em gráficos bipartidos; portanto, a bipartida não traz nada de novo.

O(|C|n2)

M. kanté
fonte