algorithm - 最小化连接到多条边的顶点数的生成树？

Question

是否有一种算法可以找到一个无向图的生成树，它可以最大限度地减少连接到一条以上边的顶点数？

例如，给定一个 4 x 4 的网格图，我们想要找到像左边那样的生成树(它有 7 个顶点连接到一条以上的边)而不是右边的生成树(有 12 个顶点):

编辑:如果我们只考虑平面图(甚至只考虑网格图)，这个问题会不会更简单？

Answer 1

正如 Evgeny 在评论中指出的那样，这被称为 maximum leaf spanning tree problem .我已经链接到关于非常密切相关的连通支配集问题的维基百科文章，这是找到最小顶点集的问题，该顶点集 (i) 诱导连通子图 (ii) 满足命题，对于所有其他顶点 v ，集合中的某些顶点与 v 相邻。通过观察表明这两个问题是解等价的，给定生成树，我们可以通过删除叶子(具有恰好一个连接的顶点)来构造一个连接的支配集，并给出一个连通支配集，我们可以提取诱导子图的生成树并将其他顶点附加为叶子。

不幸的是，这两个问题都是 NP 难的，并且在平面图的限制下它们仍然是 NP 难的。我对有关连通支配集的文献特别不熟悉，但我的猜测是存在三个角度。

1. 可证明“快速”的指数时间精确算法/近似算法。
2. 无法证明速度很快(例如整数规划)但在实践中表现良好的精确算法。
3. 启发式。

#1 可能看起来像一个奇怪的分组，但在平面图文献中往往会发生的是，确切的算法被用作近似算法内部的子程序，通常是通过 Brenda Baker 提出的一种称为移位的技术。平面图的一个特性是称为树宽的参数以 O(sqrt(n)) 而不是 n 为界，并且存在运行时间指数是小得多的树宽的函数的动态程序。 (例如，在网格上，您可以逐行运行 DP。树分解机制将其推广到任意平面图。)

如果不知道实例是什么样子，甚至可能没有对它们进行试验，就很难就最佳类(class)向您提出建议。我可能会选择 2 号门，但我不确定好的配方是什么样的。好消息是大部分算法复杂性都被抽象到您将要使用的求解器库中。这是未知质量的公式。

对于所有顶点 v，如果 v 是非叶子且 则让 x_v 为 1 >0 如果 v 是叶子。支配集部分很简单。

minimize sum_v x_v
subject to
for all v, sum_{w such that w = v or w ~ v} x_w >= 1
for all v, x_v in {0, 1}

这里我使用 ~ 来表示“毗邻”。强制执行连接性约束比较棘手。我能想到的最简单的方法是按原样求解整数程序，然后寻找两个顶点 s 和 t 都被选中但在解决方案中没有连接，计算不包括所选顶点的分隔符中 s 和 t 之间的最小顶点分隔符 U，输入约束

(1 - x_s) + (1 - x_t) + sum_{v in U} x_v >= 1

然后重试。

我对使用指数级变量的方法更有希望，但实现起来可能要困难得多(行和列生成)。选择一个顶点 r 将被强制为非叶子(猜测或尝试所有可能性)。每个以 r 为端点的简单路径 P 都有一个变量 y_P。

minimize sum_v x_v
subject to
for all v, for all P having v as an interior vertex,
  x_v >= y_P
for all v, sum_{P having v as an endpoint} y_P >= 1
for all v, x_v in {0, 1}
for all P, y_P in {0, 1}