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.



How to find a minimal rooted tree with maximial sum vertex weights?
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.


