从完全图最大化移除边保留k-plex性质：是否存在多项式算法？

核心结论 #

当节点集合固定时，这个问题存在多项式时间算法——它可以转化为带度数约束的最大权边选择问题，属于多项式可解范畴。

问题转化与算法实现思路 #

原问题要求移除边的权值总和最大，同时保持k-plex性质（每个顶点最多不与k个顶点相邻，即每个节点最多移除k条边）。这等价于：

• 在完全图的边集中，选择一个边子集S，满足每个节点在S中的度数≤k，且S的总权值最大。

这个问题可以通过两种多项式时间方法解决：

1. 流网络建模：
   • 构建包含源点、边节点、原图节点、汇点的四层网络；
   • 源点到每个边节点的边容量为对应边的权值；每个边节点连接其对应的两个原图节点，容量设为无穷大（或边权值）；每个原图节点到汇点的边容量为k；
   • 求解该网络的最大流，对应的最小割所选中的边子集就是最优的移除边集合。
2. 线性规划求解：
   • 对每条边定义0-1变量（1表示移除，0表示保留）；
   • 约束条件为每个节点对应的变量之和≤k；
   • 目标函数为所有边变量乘以对应权值的总和最大化。
   • 由于该问题的约束矩阵是全幺模的，线性规划的最优解自动为整数解，可通过多项式时间的线性规划算法求解。

与一般k-plex编辑问题的复杂度差异 #

一般k-plex编辑问题需要同时确定节点集合和边的编辑操作，因此是NP-hard；而本次问题中节点集合固定，仅需满足每个节点的移除边数约束，不存在节点选择的复杂度，因此问题难度大幅降低，从NP-hard降至多项式时间可解。

贪心策略的局限性 #

你提到的反例确实暴露了贪心算法的缺陷：在5节点clique构造3-plex（每个节点最多移除2条边）的场景中，若存在一条高权值边和多条次高权值边，贪心优先选高权边会占用两个节点的部分移除额度，导致最终能选的边总数和总权值不如最优解。比如：一条边权为3，其余8条边权为2，贪心选这条权3的边后，最多再选3条权2的边（总权值9），而最优解是选5条权2的边（总权值10），且每个节点恰好移除2条边。这说明贪心无法保证最优，必须使用精确算法。

内容的提问来源于stack exchange，提问作者Mamiglia