有向无环图中最大权重连通子图

Question

我正在研究涉及逻辑电路的研究问题（可以表示为DAG）。 DAG中的每个节点都有一个给定的权值，可能为负数。 我的目标是找到一个连接的子图，使节点权重的总和最大。

显然，对于给定边权的最大权重连接子图问题是NP难的，但我希望指出的是，它是由于有向无环特性和我处理的是节点权重而非边权重，使得该问题变得更加容易。 请问如何开始解决这个问题？

谢谢。

- Mike Henry

---

你的典型图有多大？有多密集？你预计会有多少节点具有负权重百分比？ - NPE

你对“连通子图”的定义是什么？你的意思是子图的无向版本是一个连通分量，还是存在一个源节点使得所有其他节点都可以从该源节点到达子图中？ - templatetypedef

实际上，在DAG中不可能存在具有多个顶点的强连通分量，所以您可能是指无向意义下的连通性...请确认。 :-) - ShreevatsaR

请注意，如果您的DAG只是一个有向路径，则Kadane算法（http://en.wikipedia.org/wiki/Maximum_subarray_problem）提供解决方案。我怀疑对此进行修改可能会导致正确的答案。 - mhum

Answer 1

您提到的问题是NP-hard问题，参考文献为Trey Ideker、Owen Ozier、Benno Schwikowski和Andrew F. Siegel撰写的论文“Discovering regulatory and signaling circuits in molecular interaction networks”，发表于2002年Bioinformatics杂志第18卷233-240页，并请参阅其补充资料：http://prosecco.ucsd.edu/ISMB2002/nph.pdf。

- marc

Answer 2

第一种方法，将每条边分配给起始节点的倒数权重，并应用最短路径算法，如Bellman-Ford。Dijkstra算法不适用于某些边可能为负数的情况。

第二种方法，从每个叶节点开始，在每条边上添加“标签”，以跟踪所有涉及节点的ID和总权重。无需标记节点，因为保证每个节点仅在每个从叶子开始的链中访问一次。例如，给定以下有向无环图（自上而下定向），其中每个节点的权重为1：

                         A     G
                        / \   /
                       /   \ /
                      B     C
                      |    / \
                      D   E   F
                           \ /
                            H

从A到B的边将被标记为{{D,B,A},3}，从A到C的边将有两个标记{{H,E,C,A},4}和{{H,F,C,A},4}。

在此预处理之后，找到每个根节点的最大权重路径。这些信息包含在它们的出边标记中。

- Soronthar

---

在DAG中查找哈密顿路径是否是NP难问题？我认为你不能将任意的哈密顿路径实例归约到这个问题，因为我们只关心DAG。 - templatetypedef

图形是有向的这一事实并不改变问题的NP-完全性质。但问题处理的是DAG而不是任意图形，这使得解决算法可以进行一些巧妙的优化。 - Soronthar

抱歉，让我重新表述一下 - 我的印象是有向无环图的哈密顿路径问题不是NP难的，因为有一个简单的多项式时间算法可以解决它，所以说这个问题可以用来解决DAG的哈密顿路径问题并不能说明它的复杂度。 - templatetypedef

额，实际上我不理解你的任何方法。为什么这个问题等同于找到任意一种哈密顿路径，当一个解可能只包含图中很少的节点？当解可能根本不是路径时，它与最短路径算法有什么关系？ - ShreevatsaR

抱歉，我的错。已删除对哈密顿路径替代方案的引用。 - Soronthar

Answer 3

我认为如果给定边权的最大权重连通子图问题是NP难的话，你的问题也是NP难的。你可以将节点权重问题转化为边权问题。

1)Lets say that your nodes have weights wn1,wn2,wn3,....wnN; where N is # of nodes.

2)Lets also say that the edges can be represented by e1,e2,e3,...eE; E- # of edges.

The weight of the edge ei:nj->nk can be defined as F(wnj,wnk), the function being
arbitrary. For simplicity we can assume wei=wnj+wnk.

Now if we assume that all node weights are independent and non-identical, then we
can say the same about the edge weights. As a DAG with non-identical edge weights
is NP hard, your problem too is. 

Having said that, I think you should proceed in the following way:
1)Look for similarity in node weights for your particular problem. If there are any,
try to look up the literature for similar problems. 

2)If they are hard to find, I suggest you translate your node weight problem to edge 
weight one, and see how the similarity in node weights translates to edge weights
problem and see what simplification can you apply to this problem, again from 
literature.

希望这能有所帮助。

- Brahadeesh

Answer 4

你提到连接的子图应该是“最大”的。为此，贪心地选择一个顶点并将其扩展直到无法再扩展。这可以确保最大性。但是，如果你的意思是“最大值”，那么问题可能是NP完全问题。另外，让我提醒你，节点加权图比边加权图更通用。为前者构建的每个算法都适用于后者，但反之则不总是成立。这很容易理解。你可以自己试试。

根据我的理解，我认为这个问题在P中。如果正确的话，那么提示是使用DAG的一些特殊属性（因为你正在研究这个问题，这似乎是一道讲义上的问题）。对于一般的图形，这可以归约为斯坦纳树，因此它是NP-Cmplete问题（实际上也适用于平面图）。

- singhsumit