所望のセットを生成するセットの交差点を効率的に見つける

Question

セットの収集 $ \ {s_1、s_2、\ dots、s_n \} $ のすべての "縮小"交差点を見つけるすべての "縮小"の交差点を見つけます。希望のセット $ \ {x \} $ "結果として。 「縮小」交差点は、 $ s_i \ cap s_j \ cap \ dots \ cap s_k={x \} $ の間の交差点として定義されます。交差点内のいずれかのセットは、結果を目的のセット $ \ {x \} $ から他のものに変更されます。

たとえば、sets $ \ {a、b、c、d、e、f \} $ のコレクションの場合は、

$ 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 \} $ 、

$ f={a、b、c、d、e \} $ 、そして

• $ A \ cap b \ cap e={x \} $ は、 $ aからの交差点です。 \キャップB. ={c、d、g、x \} $ 、 $ a \ cap e={f、x \} $ 、およびspan class="math-container"> $ b \ cap e={t、x \} $ 。セット $ A $ 、 $ b $ 、または $ e $ からの $ a \ cap b \ cap e $ は、目的のセット $ \ {x \} $ とは異なる結果が得られます。
• $ c \ cap d \ cap e={x \} $ は交差点の減少ではありません。 $ c \ cap e={x \} $ 。セットの削除 $ d $ の交差点から $ c \ cap d \ cap e $ は、結果として希望のセット $ \ {x \} $ を生成します。

私の質問は、セットの集まりを考えると、所望のセットを生じるそれらのセット間のすべての減少した交差点を見つけるための最も効率的なアルゴリズムは何ですか？

希望のセットに単一の要素しかないかどうかは関係ありません。この例では、単純さのために単一の要素 $ x $ を使用しました。

Answer 1

あなたの問題は、すべての包含最小セットカバーの列挙れと同等です。A-SET ">こちら。

交差点がいくつか設定されているセットのすべてのコレクションを探しているとします $ t $ 。関連するすべてのセットには、 $ t $ を含める必要があるため、 $ t $ を含むすべてのセットを考慮することができます。 $ t $ を削除します。これは、 $ t=afthyset $ です。

現在 $ u $ をすべてのセットの共用体にすることができます。セットの集合の交差点は空のIFFであるIFFが $ u $ です。言い換えれば、すべてのセットを補完する場合は、包含最小限のセットカバーに興味があります。