NP完全？具有特定约束的图的最佳图嵌入

Question

我有一个基于网格的图,其中节点和边占据单元格.边缘可以交叉,但不能在同一方向上相互移动.

让我们说我想优化图形,以便边缘覆盖的距离最小化.我目前正在使用A*搜索每个连接,但算法是贪婪的,不提前计划.请考虑下面的图表,其中更改连接的顺序(请注意,对于任何给定边,可以有多个最短路径,请参阅绿色和紫色连接).

我的直觉说这是NP-Complete,并且需要进行详尽的搜索,随着图形的大小增加,这将是非常昂贵的.但是,我没有办法表明这一点,并且它与通常涉及最小化交叉的其他图形嵌入问题并不完全相同.

Answer 1

你没有真正描述你的问题，你的形象也消失了，但你的问题听起来像是最小的 T 型连接问题。

最小 T 连接问题在图 G 上定义。给定一个偶数大小的集合 T，并且您试图找到图的子图，其中 T 的顶点具有奇数度，其他顶点具有偶数度程度。您的边上有权重，并且您正在尝试最小化子图中边的权重之和。

令人惊讶的是，由于与非二分匹配问题的紧密联系，最小 T 型连接问题可以在多项式时间内解决。也就是说，如果找到 T 的顶点之间的所有对最短路径，则通过 T 中的顶点的最小权重完美匹配获得最小 T 连接，其中两个顶点之间有一条边，其长度为最短路径的长度在G。

最小 T 型连接将是路径的集合。如果两个不同的路径，比如 a->b 和 c->d，使用相同的边 uv，那么它们可以被 a->u->c 和 b->v->d 替换，并减少 T 的成本-加入。所以它不会两次使用同一条边。