3
$\begingroup$

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

A graph

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.)

Improve this question
$\endgroup$
2
  • 1
    $\begingroup$ 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 $\endgroup$
    – Mengfan Ma
    Commented Jul 10, 2022 at 8:21
  • $\begingroup$ 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 $\endgroup$
    – Dan
    Commented Aug 16, 2022 at 21:45

1 Answer 1

Reset to default
5
$\begingroup$

The problem is equivalent to the node-weighted version of the Steiner tree problem. Happy nodes correspond to terminals, and non-removed unhappy nodes correspond to Steiner vertices.

This problem is NP-hard even for planar graphs. The NP-hardness can be proven by reducing the edge-weighted Steiner tree problem: insert one vertex in the middle of each edge.

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.

Improve this answer
$\endgroup$

Not the answer you're looking for? Browse other questions tagged or ask your own question.