Trovare in modo efficiente le intersezioni dei set che producono un set desiderato

Question

Data una raccolta di set $ \ {s_1, s_2, \ dots, s_n \} $ , trova tutte le intersezioni "ridotte" tra quei set che producono il Set desiderato $ \ {x \} $ come risultato. Un'intersezione "ridotta" è definita come intersezione tra i set in cui $ s_i \ cap s_j \ cap \ dots \ cap s_k={x \} $ , tale che rimozione Qualsiasi set di set nell'intersezione cambia il risultato dal set desiderato $ \ {x \} $ a qualcos'altro.

Ad esempio, per la raccolta di set $ \ {a, b, c, d, e, f \} $ , dove:

$ a={c, d, f, g, x \} $ ,

$ B={c, d, g, p, t, x \} $ ,

$ c={e, i, x, y \} $ ,

$ d={a, i, o, p, q, w, x} $ ,

$ e={f, t, w, x \} $ e

$ f={a, b, c, d, e \} $ , quindi:

.
• $ a \ cap b \ cap e={x \} $ è un intersezione ridotto, perché $ a \ Cap B. ={c, d, g, x \} $ , $ a \ cap e={f, x \} $ e $ B \ cap e={t, x \} $ . Rimozione di uno dei set $ A $ , $ B $ o $ E $ dall'intersezione $ a \ Cap B \ Cap E $ produce un risultato diverso rispetto al set di set $ {x \} $ .
• $ c \ cap d \ cap e={x \} $ non è un intersezione ridotto, perché $ c \ cap e={x \} $ . Rimozione del set $ D $ dall'intersezione $ c \ cap d \ Cap E $ restituisce ancora il set di set $ \ {x \} $ come risultato.

La mia domanda è: data una raccolta di set, qual è l'algoritmo più efficiente per trovare tutte le intersezioni ridotte tra quei set che producono un set desiderato?

Si noti che non importa se il set desiderato ha solo un singolo elemento o meno. In questo esempio, ho appena usato un singolo elemento $ x $ per semplicità.

Answer 1

Il tuo problema è equivalente a elencare tutti i coperchi impostati minimi di inclusione, un problema indirizzato a qui .

Supponiamo che tu stia cercando tutte le raccolte di set il cui intersezione è un set di $ T $ .Tutti i set rilevanti devono contenere $ T $ , in modo da poter considerare tutti i set contenenti $ T $ ,e rimuovere $ T $ da tutti loro.Questo riduce al caso $ t=vuoto set $ .

Ora Let $ U $ Sii l'unione di tutti i set.L'intersezione di una raccolta di set è vuota IF L'Unione dei loro complementi è $ U $ .In altre parole, se completi tutti i set, allora sei interessato a copre set minimal incluso.