我有一种特殊的图问题，并且（没有图算法的背景）我想知道这种问题在文献中是如何被称为的，以及存在哪些算法来解决它。

我有一个由顶点组成的无向图$V$和边缘$E$. 每条边都有潜力$p_e \in [0..1]$

独立于边缘潜力，还有边缘权重$w_e \in \{0,1\}$打开/关闭一条边并连接或断开两个顶点。一个顶点的 1-weight-edges 的数量让我们调用$n$，它是顶点的“连通性”（或“子图度”）。

在我们的问题中，给出了边势，边权重是我们所寻找的。

然后我们打电话$s_e=p_e*w_e$边缘的“力量”。此外，对于任何两个顶点，如果存在间接连接，则间接连接的强度是所有强度的乘积$s_e$沿着路径。两个顶点之间最短连接的强度让我们调用$t_e$.

所以，问题是：对于给定的全局$n$（所有顶点都一样）我怎样才能找到权重$w_e$对于每条边，都会导致图形的“最佳”互连，即最大化总和的边$t_e$?

换句话说：有一个给定的（通常很小）$n$, 我想选择$n$在每个顶点的许多现有边中，结果图是“很好”连接的。这意味着该算法将倾向于将两个顶点连接起来$p_e$用更高的连接顶点$p_e$但是谁已经有了很好的间接联系。

更新：根据下面的评论，我正在寻找$n$- 正则边诱导子图，最大化所有的总和$t_e$.

我有一种预感，这可能很难 NP，但任何近似解决方案也将不胜感激。