Maximum weight connected subgraph in an directed acyclic graph

I am working on a research problem involving logic circuits (which can be represented as DAGs). Each node in the DAG has a given weight, which can be negative. My objective is to find a connected subgraph such that the sum of the node weights is maximal.

The maximum weight connected subgraph problem given edge weights is NP-hard apparently, but what I am hoping is that the directed-acyclic nature and the fact that I am dealing with node weights rather than edge weights makes the problem somewhat easier. Can someone point me in the right direction of how to start attacking this problem?

Thanks

---

the problem you mentioned is NP-hard, see: “Discovering regulatory and signaling circuits in molecular interaction networks” by Trey Ideker, Owen Ozier, Benno Schwikowski, and Andrew F. Siegel, Bioinformatics, Vol 18, p.233-240, 2002

and the supplementary information to this paper: http://prosecco.ucsd.edu/ISMB2002/nph.pdf

---

First approach, Assign to each edge the inverse of the weight of the starting node, and apply a shortest path algorithm like Bellman-Ford. The Dijkstra's algorithm won't work as some edges can be negative.

Second approach, starting on each leaf node, add "tags" to each edge that keeps track of the ids of all the nodes involved, and the total weight. There is no need to mark the node, as each node is guaranteed to be visited only once for each chain starting on the leafs. For example, given the following Acyclic Directed graph (directed top to bottom) where each node weights 1:

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

The edge between A and B will be tagged {{D,B,A},3}, the edge between A and C will have two tags {{H,E,C,A},4} and {{H,F,C,A},4}.

After this pre-procesing, find the greatest weight path for each root node. The information is in the tags of their outbound edges.

---

You mentioned that connected that connected subgraph should be "maximal". For this greedily choose a vertex and grow it until you cannot grow. this assures maximality. However if you mean "maximum" then the problem might be NP_Complete. Also let me remind you that node weighted graphs are more general than edge weighted graphs. Every algorithm built for the former is applicable to later but vice-versa is not always true. This is very easy to see. Try out yourself. What i understand the problem, i feel it is in P. If that is correct then the Hint for that is to use some special property for DAGs (which u shud know since ur researching and this seems a lecture notes problem). For general graphs, this is reducible to steiner trees so it is NP-Cmplete(infact also for planar graphs).

链接地址: http://www.djcxy.com/p/35278.html

上一篇: 正加权有向无环图的边最短路径

下一篇: 有向无环图中连接子图的最大权重