论文标题
针对特殊Digraph约束的子集总和问题的解决方案
Solutions for Subset Sum Problems with Special Digraph Constraints
论文作者
论文摘要
子集总和问题是组合优化中最简单，最基本的NP硬性问题之一。我们考虑了此问题的两个扩展：digraph约束（SSG）的子集总和问题和弱挖掘约束（SSGW）的子集总和问题。在这两个问题中都有一个挖掘图，并将大小分配给顶点。在SSG中，我们希望找到一个顶点的子集，其总尺寸不超过给定容量，并且如果至少一个前任是解决方案的一部分，则包含顶点。在SSGW中，我们希望找到一个顶点的子集，其总尺寸不超过给定容量，并且如果其所有前任都是解决方案的一部分，则包含顶点。 SSG和SSGW最近由Gourves等人引入。他们研究了针对定向的无环图和定向树的复杂性。我们表明，即使在定向的共编照术和最小的串联挖掘图上，这两个问题都是NP固定的。此外，我们为SSG和SSGW提供了伪 - 多项式溶液，并具有由定向的共包和串联平行挖掘物给出的Digraph约束。
The subset sum problem is one of the simplest and most fundamental NP-hard problems in combinatorial optimization. We consider two extensions of this problem: The subset sum problem with digraph constraint (SSG) and subset sum problem with weak digraph constraint (SSGW). In both problems there is given a digraph with sizes assigned to the vertices. Within SSG we want to find a subset of vertices whose total size does not exceed a given capacity and which contains a vertex if at least one of its predecessors is part of the solution. Within SSGW we want to find a subset of vertices whose total size does not exceed a given capacity and which contains a vertex if all its predecessors are part of the solution. SSG and SSGW have been introduced recently by Gourves et al. who studied their complexity for directed acyclic graphs and oriented trees. We show that both problems are NP-hard even on oriented co-graphs and minimal series-parallel digraphs. Further, we provide pseudo-polynomial solutions for SSG and SSGW with digraph constraints given by directed co-graphs and series-parallel digraphs.
