How to find a minimal rooted tree with maximial sum vertex weights?

Question

I have an undirected grid graph, nxm, where each vertex has a value (positive or negative) and I need to find the tree rooted at vertex (1,1) that maximizes the sum of these values with a minimal number vertices.

The tree do not have to go through all nodes, although the tree can pick a negative vertex so it can pick a positive one.

Edges have no value.

I will appreciate any advice.

Answer 1

The optimal solution can be found as follows:

• repeatedly delete from the vertices with negative weight the one, that has minimal weight and whose removal doesn't disconnect the graph, i.e. that isn't an articulation vertex.
• replace each connected component of the subgraph induced by edges, that are ajacent to two vertices with positive weight, by a single vertex and assign to it the sum of all vertex weights in that component.
• replace the paths between two vertices with positive weight by an edge, whose weight equals the sum of negative vertex weights on that path.
• in the resulting tree-graph define the vertex that "contains" $(1,1)$ as the root

• start a depth-first search from the root node:

  • after returning from descending into each of the children of a vertex $v$, either

    • add the sum of the weights $\omega(v)$ and $\omega(e)$ of $v$ and of the edge $e$ adjacent to $v$ and to $v$'s father-vertex $u$ if $\omega(v)+\omega(e)\gt 0$, i.e $\ \omega(u)=\omega(u)+\omega(e)+\omega(v)$ in that case

    • otherwise add nothing to the father-node weight and mark $e$ and $v$ as deleted

• finally replace the tree-nodes and edges that aren't marked as deleted, by the corresponding vertices and edges of the original graph to obtain the optimal solution.