在一般情况下，找到图的最大独立子集是 NP Hard。
但是，请考虑以下图表子集：
创建一个 NxN 单位正方形单元格。
通过创建与每个单元格对应的顶点来构建图 G。请注意，有 N^2 个顶点。
如果两个顶点的单元共享一条边，则在两个顶点之间创建一条边。注意有 2N(N-1) 条边。
G 的最大独立子集显然是一个棋盘格模式。如果 R+C 为奇数，则第 R 行第 C 列的单元格是其中的一部分。
现在我们通过复制 G 并删除一些顶点和边来创建一个图 G'。（如果您删除一个顶点，当然也会删除它结束的所有边。另请注意，您可以删除一条边而不删除它结束的顶点之一。）
通过什么算法我们可以找到 G' 的最大独立子集？