Maximum weight connected subgraph in an directed acyclic graph

I am working on a research problem involving logic circuits (wh开发者_Go百科ich 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 u r 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).

---

I think your problem is NP hard if the maximum weight connected subgraph problem given edge weights is NP hard. You can reduce the node weight problem to the edge weight problem.

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.

I hope this helps.