有人见过这样的 NP 图问题吗？

Question

我有以下基于图表的问题：

1. 输入：正整数 K 和 L，无向图 G
2. 我必须从此图中选择 K 个顶点
3. 在每对选定的 K 个顶点之间的路径中必须至少有 L 个顶点 i。e.每两个所选顶点之间必须有一个由至少 L 个顶点组成的“空间”。

当然，对于给定的问题实例，上述内容可能是不可能的，那么我必须检查一下。我非常确定这个问题是 NP 甚至 NP 完全问题，因为它与具有长度约束的路径有关。您遇到过类似的问题吗？你知道如何将其简化为一些更知名的问题，可能是 NP，例如。G。顶点覆盖或图形着色？

另请注意，我的图是一个网格图，它可能不是“完整的”，而是完整矩形网格的子图。

Answer 1

这被称为距离 - $ d $ 独立集，即，您正在寻找一个独立的大小集 $ k $ 解决方案中每两个元素之间的距离至少 $ d $ 。

即使在[1]的平面图上，问题也是NP-Temply，但我不知道其在部分网格上的复杂性。

关于缩减，您可以采用 $ d $ 'th 图表的电源并找到一个（距离-1）独立集合。索赔是这里的任何解决方案都是距离 - $ d $ 在原版中独立集，但您需要验证这个。

---

[1] eto，hiroshi，fengrui gu，和eiji miyano。 “距离 - $ d $ 与二分和十字图形的独立设置问题。”组合优化27杂志，不。 1（2014）：88-99。

Answer 2

在特殊情况下，如果 $L=1$, ，这是 最大独立集问题, ，这在一般图上是 NP 困难的。因此，你的问题在一般图上也是 NP 难的。

您可以尝试希望有一种特定于您所拥有的图类的算法（我认为最大独立集 可以在二部图中有效地计算, ，并且网格图是二分的，因此您可以尝试推广该算法），或者您可以尝试使用最大独立集/团的标准算法，或者您可以尝试使用 SAT 求解器。将其表述为 MaxSAT 实例应该很容易：对于距离内的每对顶点都有一个子句 $L+1$ （或更少），并且您要求 SAT 求解器最小化设置为 true 的变量数量。

Answer 3

似乎检查是否存在G的k顶点子图，它可以使用图形着色问题的规则可调整。我的意思是，如果所有k顶点都有相同的颜色，则满足您的条件。

由于NP-Complete中的图形着色U可以验证多项式时间中的给定解决方案。

所以也许，只许这是一个第一眼回答，你必须

1 - 检查你的图表是否是可色的

2 - 使用一组k顶点搜索颜色