Menu
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
757
The resulting meta-graph must be a dag. The reason is simple: a cycle containing several strongly connected components would merge them all into a single, strongly connected component. Restated, Property Every directed graph is a dag of its strongly connected components.
The maximum number of edges in a DAG with n vertices is Θ(n2).
Theorem Every finite DAG has at least one source, and at least one sink.
A directed graph is acyclic if and only if it has no strongly connected subgraphs with more than one vertex, because a directed cycle is strongly connected and every non-trivial strongly connected component contains at least one directed cycle.
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
113
If you love us? You can donate to us via Paypal or buy me a coffee so we can maintain and grow! Thank you!
Donate Us With
