Delete k vertices from a graph such that it remains connected Given an undirected graph G(V,E) where each V has an integer value, remove k number of vertices such that there is a path between all the remaining vertices and the sum of the remaining values are maximal. In other words, remove k vertices with the lowest sum of values. Solution must be optimal.
I am wondering what algorithm I can use for this. I am thinking of backtracking.
 A: If the graph is a grid with $2$ rows and $N$ columns, then a dynamic programming approach should work.
The idea is to compute recursively the answers to questions similar to the following one: considering only the subgraph given by the first $n$ columns, what is the maximum sum you can get adding the values of $q$ distinct connected vertices?
There is a problem, however, if you try to answer recursively the questions exactly as stated above. I'm not writing the details here, but you will have troubles keeping track of the connectedness of the set of vertices you are choosing. The tecnique to get around this kind of problems is to make the questions more precise adding restrictions (consequently you will have to consider a larger number of questions). In this specific case you should consider in addition questions like the following: in the subgraph given by the first $n$ columns, what is the maximum sum you can get adding the values of $q$ distinct connected vertices, with the restriction that you have to include the upper (or lower) vertex in the $n-$th column?
