将一组带有约束的符号划分为最小数量子集的算法

Question

我有一个集合 S={a,c,d,e,f,j,m,q,s,t} 有一个约束 C={am,cm, de,df,dm,ds,ef,em,eq,es,et,fj,fm,fs,jm,js}。 C 中的 xy 表示 x 和 y 不能在同一个子集中。我想要一种算法将集合 S 分成子集 Sj，这样:

1.Sj的数量最小化

2.每个子集大小的差异尽可能大

例如在这种情况下，{{q,a,c,d,j,t},{m,s},{f},{e}} 和 {{a,c,e,j},{m,s,q,t},{d},{f}} 都满足 1，但第一个是最优的。

来自计算机科学背景，我想知道数学家是否为这个问题设计了算法。

Answer 1

据我了解，您的任务可以改写为:找到图 G=(S, C) 的顶点 S' 的最大独立子集；对图 G'=G\S' 重复该步骤。

众所周知(@tobias_k 在他的评论中也指出)图的最大独立集 是 NP-hard 问题(因为它等同于著名的 clique-problem)。