algorithm - 最大化子图中心度的算法

Question

假设我有一些带有节点和无向边的图（这些边可能有一个与之相关联的权重）。
我想找到所有（或至少一个）连通子图，在加权边之和为 有算法可以做到这一点吗？

Answer 1

一次快速的搜索把我带到了this description of degree centrality。结果表明，顶点的“度中心度”只是它的度（邻域计数）。
不幸的是，你的问题是“AA>”，所以不太可能存在任何能够快速解决每个实例的算法。首先注意，假设边权重为正，任何最优解中的边必然形成一棵树，因为在任何非树中，您可以删除至少一条边而不破坏连接性，这样做将降低子图的总边权重。（因此，作为一个积极的衍生：如果计算输入图的最小生成树，发现它的总权重 让我们为你的问题制定一个决策版本。给定一个图G＝（v，e），在边上有一个正的（i假定）权，一个数x和一个数y，我们想知道：G是否存在一个连通子图G’＝（v’，e’），使得E’中的边权之和最大为X，V′（W.R.T.G）的和的总和至少是y？（很明显，这并不比原来的问题难：如果你有一个算法来解决你的问题，那么你可以运行它，把它找到的子图中的顶点的度数加起来，并将其与Y进行比较来回答“我的”问题。）
这里是np-hard NP-hard问题的一个简化，我们得到了一个图g=（v，e）的边上有正的权重，它的顶点的子集s，和一个数字k，任务是确定是否可以使用总权重最大为k的边子集连接s中的顶点（如我上面所示，如果g中的所有度数之和都是d，那么我们需要做的就是将g转换为问题的输入：对于s中的每个顶点，我们添加足够多的新的“压载”顶点，每个顶点通过权重x+1的边仅连接到s_i，以使s_i的度数达到d+1。我们把X设为k，把Y设为| S |（d+1）。
现在，假设Steiner树问题的解决方案是肯定的，也就是说，存在一个具有总权重的边集k＝k，它连接了S.中的所有顶点，在这种情况下，很清楚，在上面构造的问题的实例中，相同的子图（可能是其他的）连接了s中的所有顶点，因为s中的每个顶点都有d+1阶，所以总的阶数至少是s（d+1），所以你的决策问题的答案也是肯定的。
在另一个方向上，假设你的决策问题的答案是肯定的，也就是说，存在一个具有总权重<＝x（＝k）的边的子集，它连接一组具有至少约为s（d＋1）的顶点的集合。我们需要证明，这意味着对原始steiner树问题的肯定回答。显然，只要证明满足上述条件（即边的总权重<=k，顶点的总度>=| S |（d+1））的任何子图的顶点集V'包含S（可能在其他顶点中）因此，让V'是这样一个解的顶点集，并相反地假设S中有一些顶点u不在V中但是，我们所能做的最大程度的和就是把图中所有其他的非压舱顶点都包括在v'中，这将给出至多（s-1）（d+1）+d的度的总和（第一项是s中其他顶点的度和；第二项是g中所有非s顶点的度和的上界；请注意，我们添加的压舱顶点都不能在子图中，因为包含它们的唯一方法是使用权重X+1的边，这显然是我们做不到的）但很明显（| S |-1）（d+1）+d=| S |（d+1）-1，严格小于| S |（d+1），这与我们的假设相矛盾，即V'的学位总数至少为| S |（d+1）因此，s是v'的子集，因此可以使用相同的边子集来连接s中的顶点，总权重不超过k，也就是说，steiner树问题的答案也是肯定的。
因此，对任何一个问题的肯定回答意味着对另一个问题的肯定回答，反过来又意味着对任何一个问题的否定回答意味着对另一个问题的否定回答。因此，如果能够在多项式时间内解决问题的决策版本，则意味着图问题中NP-hard Steiner树的多项式时间解这意味着问题的决策版本本身是np难的，优化版本也是np难的（正如我上面所说的，优化版本至少是np难的）。（决策表也 Steiner Tree in Graphs，因为可以在多项式时间内轻松验证是的答案。）
旁注：一开始我认为我从n p难背包问题中得到了一个非常直接的简化：给定一个n个权重w_1，…，w_n和一个n个利润p_1，…，p_n的列表，使一个中心顶点c和n个其他顶点v_1，…，v_n。对于每个v_i，用一个权重w_i的边将其附加到c，并添加p_i其他叶顶点，每一个都只有一个重量X+1的边缘连接到v_i然而，这种减少实际上不起作用，因为利润在输入大小n中是指数的，这意味着问题的构造实例可能需要指数数量的顶点，这是多项式时间减少所不允许的。