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

Question

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

给定边权重的最大权重连通子图问题显然是 NP 困难的，但我希望的是有向无环性质以及我处理节点权重而不是边权重的事实使问题变得更容易。有人能指出我如何开始解决这个问题的正确方向吗？

谢谢

Answer 1

你提到的问题是NP-hard问题，请参阅：
“发现分子相互作用网络中的调节和信号传导电路”
作者：Trey Ideker、Owen Ozier、Benno Schwikowski 和 Andrew F. Siegel，
Bioinformatics，第 18 卷，第 233-240 页，2002 年

以及本文的补充信息：
http://prosecco.ucsd.edu/ISMB2002/nph.pdf

Answer 2

第一种方法，为每条边分配起始节点权重的倒数，并应用最短路径算法，例如 贝尔曼-福特。 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}。

经过此预处理后，找到每个根节点的最大权重路径。该信息位于其出站边缘的标签中。

Answer 3

您提到连接的连接子图应该是“最大”。为此，贪婪地选择一个顶点并使其增长，直到无法增长为止。这保证了最大化。但是，如果您的意思是“最大”，那么问题可能是 NP_Complete。另外让我提醒您，节点加权图比边加权图更通用。为前者构建的每个算法都适用于后者，但反之亦然。这很容易看出。自己尝试一下。
我对这个问题的理解是，我觉得它在 P 中。如果这是正确的，那么提示就是使用 DAG 的一些特殊属性（自从你研究以来你应该知道这一点，这似乎是一个讲义问题）。对于一般图，这可以简化为斯坦纳树，因此它是 NP-Cmplete（事实上也适用于平面图）。

Answer 4

如果给定边权重的最大权重连通子图问题是 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.

我希望这有帮助。