On a DAG Partitioning Problem
On a DAG Partitioning Problem
复制标题
关于 DAG 分区问题
DOI：
10.1007/978-3-642-30541-2_2
复制
发表时间：
2012
期刊：
影响因子：
--
通讯作者：
Abbas Mehrabian
中科院分区：
文献类型：
--
作者：
Soroush Alamdari;Abbas Mehrabian
我们研究以下 DAG 分区问题：给定一个具有弧权重的有向无环图，删除一组总权重最小的弧，以便每个生成的连接组件都有一个接收器。我们证明这个问题很难在强意义上近似：如果 $\mathcal P\neq \mathcal{NP}$ 则对于每个固定的 e>0，不存在 (n1−e) 近似算法，即使输入图被限制为具有单位权重弧、最大出度为 3 和两个汇。我们还提出了一种多项式时间算法，用于解决具有有限路径宽度的图中的 DAG 分区问题。
We study the following DAG Partitioning problem: given a directed acyclic graph with arc weights, delete a set of arcs of minimum total weight so that each of the resulting connected components has exactly one sink. We prove that the problem is hard to approximate in a strong sense: If $\mathcal P\neq \mathcal{NP}$ then for every fixed e>0, there is no (n1−e)-approximation algorithm, even if the input graph is restricted to have unit weight arcs, maximum out-degree three, and two sinks. We also present a polynomial time algorithm for solving the DAG Partitioning problem in graphs with bounded pathwidth.