二维网格子图的最大独立子集

Question

在寻找图的最大独立子集的一般情况下是NP难度。

然而考虑图的子集：

创建单元正方形单元的N×N格子。

通过创建对应于每个单元格的顶点来构建图G。注意有N^2个顶点。

如果两个顶点的单元共享一侧，则在两个顶点之间创建一条边。注意有2N（N-1）条边。

G的最大独立子集显然是一个检查模式。如果R + C是奇数，则第R行和第C列的单元格就是它的一部分。

现在我们通过复制G并去除一些顶点和边来创建图G'。 （如果你删除了一个顶点，当然也要删除它的所有边缘，并且注意你可以删除一个边而不去掉它的一个顶点）

通过什么算法可以找到G'的最大独立子集？

Answer 1

阅读here。我认为你仍然被洗脑，这仍然是NP难。由于您的学位最多只有4个，所以简单的贪婪算法会得到近似比率2.您的结果图也是平面的，所以有一个很好的近似算法（多时间中的任何固定近似比）。