有向二分图中不相交树覆盖B集的最小最大边数问题及复杂度问询

问题所属类型 #

该问题属于带约束的图覆盖与负载均衡交叉问题，更精准的归类是有向二分图的最小最大根树覆盖问题，其核心等价于：将二分图中B集合的顶点分配给A集合中相邻的顶点，每个A顶点对应一棵以自身为根的有向树（树的边数即分配给该A顶点的B顶点数量），目标是最小化所有树中最大的边数，本质是带邻接约束的最小最大负载分配问题。

问题的复杂度 #

该问题的判定版本（给定k，判断是否存在满足条件的树覆盖，使得所有树的边数不超过k）是NP完全问题，因此对应的优化版本是NP难问题，归约证明可通过经典NP完全问题完成：

• 从3-划分问题归约：给定3n个元素（对应B集合的3n个顶点），每个元素大小为s_i，总和为nT，构造A集合含n个顶点（对应3-划分的n个组），每个A顶点与所有B顶点相连（元素可分配到任意组）。此时原问题的判定版本等价于判断是否能将B顶点分成n个大小为3的子集（对应每组3个元素），这正是3-划分问题的核心，而3-划分是强NP完全问题，因此原问题判定版本为NP完全。
• 当A中顶点与所有B顶点相连时，问题退化为均匀机器调度的Makespan最小化问题，该问题已被证明为NP完全。

此外，即使限制二分图的结构（如A中顶点出度有限），只要保留“B顶点需分配给相邻A顶点”的约束，问题仍保持NP难特性。

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