グループ内の各アイテムが他のメンバーと共通の要素を共有しないようなグループタプル

Question

私はこのような現実世界の問題に遭遇しました。グループにソートする必要があるペアのリストがあります。グループのメンバーは、グループの他のメンバーと要素を共有できないという制約で、合計したグループの数を最小限に抑えたいと考えています。

ここは例です。タプルのリストは（A、B）、（B、C）、（C、A）、（D、E）、（F、G）です。 [（A、B）、（D、E）、（F、G）]、[（B、C）]、[（C、A）]の3つのグループを形成することができます。

この問題を多項式時間で最適に解くことは可能ですか？貪欲なソリューションはどれくらい悪いですか？これは別の問題として提起されている可能性がありますが、私はそれを他のものに減らす方法をかなり理解できません（グラフの色付けが気になります）。

Answer 1

前述の問題は、edge-coloring problemと考えることができます。各タプルエントリがノードであり、エッジがタプルによって与えられるグラフがあります。タプルをグループにクラスタリングすることは、端点（マッチ）を共有しないエッジのグループを見つけることに相当し、エッジカラーで同じ色を割り当てることができます。言い換えると、各エッジの色分けによってクラスタリングが行われ、各クラスタリングによってエッジの色付けが行われます。残念ながら、NP -hardは、最高の色付けを見つけるため、問題は一般的にNP -hardです。この問題の近似アルゴリズムは定数因子近似を生成しますが、P = NPがない限り、正確なアルゴリズムはありません。

タプルごとに任意の数の要素を許可するようにこの問題を一般化すると、この問題はより困難になります。この問題の一般的なバージョンは、実際にはNP -hardであり、グラフの色付けからの削減によって、実際には近似しにくいです。特定のケースの削減の例を示しますが、それは非常にうまく一般化します。

このようなグラフを考える：

A -- B -- C 
| | | 
D -- E -- F 

我々は、タプル内の各エントリは、そのノードに隣接するエッジの集合であるタプルの集合、各ノードに1つずつ、作成します。例えば、上のグラフでは、我々はこれらのタプルを形成したい：

(AB, AD) 
(AB, BC, BE) 
(CB, CF) 
(AD, DE) 
(BE, DE, EF) 
(CF, EF) 

は今、これらのタプルの2が重複していないことを想像してください。これは、それらのタプルに対応する2つのノードが隣接していてはならないことを意味する。なぜなら、それらの間のエッジはタプル内の共通要素であり、したがってそれらはクラスタ化できないからである。一方、2つのノードが隣接していない場合、それらのタプルは、同じタプル内のエッジが他のタプルに存在しないので、同じクラスタ内に一緒にグループ化することができる。

元のグラフを着色すると、タプルをクラスタリングする方法が提供されます（同じ色のノードのすべてのタプルを同じセットに入れます;それらのどれも隣接しないので競合しません）。タプルをクラスタリングする任意の方法では、色付けが行われます（クラスター内の各タプルに対応するすべてのノードを同じ色に色付けします）。したがって、クラスタの最小数を見つけることは、NP -hardであり、真の値に近いところに近づく近似アルゴリズムを認めることは知られていない元のグラフの色数を見つけることに対応する。