# Efficiently determine which nodes should leave a graph while maintaining connectedness

Suppose I have a graph with node weights, where a weight is either -1 or a positive integer. For example:

If a node has weight -1, it is "happy", and cannot be kicked out of the graph.
If a node has positive weight, it is "unhappy", and can be kicked out of the graph.

How do I efficiently calculate which unhappy nodes I should kick out of the graph in order to minimize unhappiness, i.e., the total weight of all unhappy nodes, while making sure that the graph remains connected?

For instance, in this case, I can't get rid of more than three unhappy nodes, since that would disconnect the graph. Out of the possible sets of three unhappy nodes, {10, 10, 8} disconnects the graph as well. Thus the optimal solution is removing the three unhappy nodes at bottom, so that only the two unhappy nodes at top remain. The unhappiness of the graph becomes 2 + 10 = 12, which is the minimum.

(Motivation: I was wondering how many unhappy counties can secede from a U.S. state without breaking the state into disconnected components, and got this graph problem that I can't figure out.)

• As pcpthm noted, the problem is essentially the node-weighted Steiner tree problem. The fastest algorithm in practice is to model it as an integer linear programming and solve the programming using modern solver like CPLEX or Gurobi. See this paper for more information about practically solving node-weighted Steiner tree and its variants: link.springer.com/article/10.1007/s12532-016-0111-0 Commented Jul 10, 2022 at 8:21
• It might work for small to medium-sized problems for formulate them as an integer programm and solve them with CPLEX/Gurobi/Xpess, but usually specialized Steiner tree solvers are thousands or even millions of times faster. You can find a list of specialized solvers under "External links" at https://en.wikipedia.org/wiki/Steiner_tree_problem
– Dan
Commented Aug 16, 2022 at 21:45

The Dreyfus-Wagner algorithm can be used for the node-weighted version as well, and runs in $$O(3^k \mathrm{poly}(n))$$ time where $$k$$ is the number of terminal nodes. If $$n - k$$ is small compared to $$k$$, bruteforcing Steiner vertices gives $$O(2^{n-k} \mathrm{poly}(n))$$ time bound.