不是一个完整的答案，我不知道它对你有多大用处。但这里有：
汉明距离让我印象深刻。您的问题陈述说它必须至少是 1，但它可能是 1000。只要说每个节点的集合成员资格的位编码是唯一的就足够了。
您的问题陈述没有详细说明，但您上面的解决方案表明每个节点都必须是至少一组的成员。IE。任何节点的集合成员资格都不允许使用全 0 的位编码。
暂时忽略连接的节点，不相交的节点很容易：只需使用未使用的位编码对它们进行顺序编号。把那些留到最后。
你上面的例子使用了有向边，但同样，这让我觉得是一条红鲱鱼。如果A不能和D在同一个集合中，因为A=>D，那么无论D=>A，D都不能和A在同一个集合中。
您提到至少需要 log(N) 集。您还将拥有最多 N 组。全连接图（具有 (N^2-N)/2 条无向边）将需要 N 个集合，每个集合包含一个节点。
实际上，如果您的图包含 M 维的完全连接的单纯形（M in 1..N-1），具有 M+1 个顶点和 (M^2+M)/2 个无向边，则您至少需要 M+1套。
在上面的示例中，您有一个具有 2 个顶点 {A,D} 和 1 个（无向）边 {(A,D)} 的单纯形 (M=1)。
您的问题似乎归结为在图中找到最大的完全连接的单纯形。换句话说，你有一个路由问题：你需要多少维度来路由你的边缘，所以没有交叉？这听起来不是一个非常可扩展的问题。
找到第一个大单纯形很容易。每个顶点节点都会获得一个带有自己位的新集合。
不相交的节点很容易。一旦处理了连接的节点，只需对不相交的节点进行编号，顺序跳过任何以前使用的位模式。从上面的示例中，由于 A 和 D 采用 01 和 10，因此 B 的下一个可用位模式是 11。
然后，棘手的部分变成了如何在使用新位创建任何新集合之前尽可能地将任何剩余的单纯形折叠到现有范围中。折叠时，每个节点必须使用 2 个或更多位（集），并且位（集）不得与任何相邻节点的位（集）相交。
考虑一下当向示例添加另一个节点 C 时，上面的示例会发生什么：
如果 C 直接连接到 A 和 D，那么最初的问题就变成了找到具有 3 个顶点 {A,C,D} 和 3 个边 {(A,c),(A,D),(C,D )}。一旦 A、C 和 D 采用位模式 001、010 和 100，不相交 B 的最低可用位模式是 011。
另一方面，如果 C 直接连接 A 或 D 但不是同时连接两者，则图有两个 1-单纯形。假设我们首先找到具有顶点 {A,D} 的 1-单纯形，给它们位模式 01 和 10，那么问题就变成了如何将 C 折叠到该范围内。唯一具有至少 2 位的位模式是 11，但它与 C 连接的任何节点相交，因此我们必须创建一个新集合并将 C 放入其中。此时，解决方案与上述类似。
如果 C 不相交，则 B 或 C 将获得位模式 11，而其余的将需要一个新集合并获得位模式 100。
假设 C 连接到 B 但不连接到 A 或 D。同样，图有两个 1-单纯形，但这次是不相交的。假设首先找到 {A,D}，如上给出 A 和 D 位模式 10 和 01。我们可以将 B 或 C 折叠到现有范围内。该范围内唯一可用的位模式是 11，B 或 C 都可以获得该模式，因为它们都不与 A 或 D 相邻。一旦使用 11，就不会保留设置了 2 位或更多位的位模式，我们将不得不创建剩余节点的新集合为其提供位模式 100。
假设 C 连接到所有 3 个 A、B 和 D。在这种情况下，图有一个具有 3 个顶点 {A,C,D} 的 2-单纯形和一个具有 2 个顶点 {B,C} 的 1-单纯形。如上所述，处理最大的单形后，A、C 和 D 将具有位模式 001、010、100。为了将 B 折叠到此范围内，设置 2 位或更多位的可用位模式为：011、101、110 和111. 除 101 之外的所有这些都与 C 相交，因此 B 将获得位模式 101。
那么问题就变成了：你能多有效地找到最大的全连接单纯形？
如果找到最大的全连接单纯形太昂贵，可以通过找到连接的最大最小值来为潜在的全连接单纯形设置一个近似上限：
扫过边，使用连接边的计数更新顶点。
对于每个连接的节点，创建一个最初为零的 Cn 计数数组，其中 Cn 是连接到节点 n 的边数。
再次扫过边缘，对于连接的节点n1和n2，增加n1中对应于Cn2的计数，反之亦然。如果 Cn2 > Cn1，则更新 n1 数组中的最后一个计数，反之亦然。
再次扫描连接的节点，计算每个节点可能属于的最大单纯形的上限。当您扫描节点时，您可以构建一个鸽洞数组，其中包含每个上限的顶点列表。
通过鸽巢阵列从最大到最小提取节点并将其折叠成独特的集合。
如果您的节点在集合 N 中，而您的边在集合 E 中，则复杂度将是：O(|N|+|E|+O(步骤 5))
如果上述近似值足够，那么问题就变成了：在给定要求的情况下，您如何有效地将节点折叠到现有范围中？