找到一组要删除的边，使得每个顶点的度数不超过 K 并且边权重之和最大化

Question

我有一个无向图，每条边都有权重。我想删除一组边，使每个顶点的度数最多为 K，但我想保留最大可能的边加权和。我想出了一个整数程序，它应该可以得出正确的解决方案。

我的问题是：

这个问题有名字吗？如果有，那是什么？
有没有已知的多项式时间算法可以解决这个问题？到目前为止，我还没有想出任何办法。也许我错过了一些明显的东西。

为了有趣，这里是我的整数程序。如果我犯了任何错误，请告诉我：

# given (graph, K):
# Let x[e] be 1 if we keep an edge e and 0 if we cut it

# Keep the best set of edges for each node
maximize
    sum(d['weight'] * x[(u, v)]
        for u in graph.nodes()
        for v, d in graph.node[u].items())

# The degree of each node must be less than K
subject to
    all(
        sum(x[(u, v)] for v in graph.node[u]) <= K
        for u in graph.nodes()
    )

编辑：

感谢 David Eisenstat 的帮助，我能够在

的第 2 节中找到对多项式时间算法的很好描述

Implementing Weighted b-Matching Algorithms: Towards a Flexible Software Design 作者 Matthias Muller Hannemann 和 Alexander Schwartz 发表于 WAE'98

此描述将 Pulleyblank 的 Blossom 算法的 1 匹配情况概括为 b 匹配问题（我也发现它被称为双向流）。

Answer 1

显然这称为 b 匹配问题，实际上可以在多项式时间内解决。请参阅此 cstheory 答案：https://cstheory.stackexchange.com/questions/17724/what-is-complexity-of-this-max-edge-subgraph-problem

找到一组要删除的边，使得每个顶点的度数不超过 K 并且边权重之和最大化

Finding a set of edges to remove such that that the degree of each vertex is no more than K and the sum of edge weights is maximized

algorithm

graph

mathematical-optimization

linear-programming