组合独立集/汉明距离的算法/近似

Question

输入:图 G
输出:多个独立集，使得一个节点对所有独立集的成员资格是唯一的。因此，节点与它自己的集合中的任何节点都没有连接。这是一个示例路径。
由于这里需要澄清，因此再次改写:
将给定的图划分为多个集合，使得

我可以通过它在集合中的成员资格来区分所有其他节点，例如如果节点 i 仅存在于集合 A 中，则仅集合 A 中不应存在其他节点
如果节点 j 存在于集合 A 和 B 中，则不应仅在集合 A 和 B 中存在其他节点。如果节点的成员资格由位模式编码，则这些位模式至少有一个汉明距离

如果图中的两个节点相邻，则它们不应该出现在同一个集合中，因此是一个独立的集合

例子:
B 没有相邻节点
D=>A，A=>D
解决方案:

A B/

/B D

A 的位模式为 10，并且其集合中没有相邻节点。 B 有位模式 11 且没有相邻节点，D 有 01
因此所有节点的汉明距离至少为 1 并且没有相邻节点 => 正确
错了，因为 D 和 A 是连通的:

A D B

/D B

A 在其集合中有位模式 10 和 D，它们是相邻的。 B 的位模式为 11 并且没有相邻节点，D 和 B 一样有 11，因此该解决方案存在两个错误，因此不被接受。
当然，随着图中节点数量的增加，这应该扩展到更多集合，因为您至少需要 log(n)套。
我已经写了一个转换到 MAX-SAT，为此使用 sat-solver。但条款的数量太多了。更直接的方法会很好。到目前为止，我有一个近似值，但我想要一个精确的解决方案或至少一个更好的近似值。
我尝试了一种方法，我使用粒子群将任意解决方案优化为更好的解决方案。然而，运行时间非常糟糕，结果也远非如此。我正在寻找动态算法或其他东西，但是我无法理解如何分而治之。

Answer 1

不是一个完整的答案，我不知道它对你有多大用处。但这里是:

汉明距离让我印象深刻。您的问题陈述说它必须至少为 1，但也可能是 1000。可以说每个节点的集合成员的位编码是唯一的就足够了。

您的问题陈述没有说明，但您上面的解决方案表明每个节点必须是至少 1 个集合的成员。 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套。

在上面的示例中，您有一个这样的单纯形 (M=1)，其中有 2 个顶点 {A,D} 和 1 个(无向)边 {(A,D)}。

您的问题似乎归结为在图中找到最大的全连接单纯形。换句话说，你有一个路由问题:你需要多少维来路由你的边缘，所以没有交叉？这听起来不像是一个非常可扩展的问题。

发现的第一个大型单纯形很容易。每个顶点节点都会获得一个带有自己位的新集合。

不相交的节点很容易。一旦处理了连接的节点，只需按顺序对不相交的节点进行编号，跳过任何以前使用的位模式。从上面的示例中，由于 A 和 D 取 01 和 10，因此 B 的下一个可用位模式是 11。

然后，棘手的部分变成如何在使用新位创建任何新集合之前将任何剩余的单纯形尽可能多地折叠到现有范围内。折叠时，每个节点必须使用 2 个或更多位(集)，并且这些位(集)不得与任何相邻节点的位(集)相交。

考虑一下当向示例中添加另一个节点 C 时，上面的示例会发生什么情况:

如果 C 直接连接到 A 和 D，那么初始问题就变成了找到具有 3 个顶点 {A,C,D} 和 3 个边 {(A,c),(A,D),(C,D) 的 2-单纯形)}。一旦 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))

如果上述近似值足够，问题就变成: 根据要求将节点折叠到现有范围的效率如何？