2

I'm trying to solve a variation of the minimum spanning tree problem; I have a graph where there are certain key nodes and optional nodes. Each optional node has a weight and we need to find a subset of the nodes which spans all the key nodes while minimizing the total weight of the optional nodes. Since the key nodes are mandatory they don't have weights. The edges also don't have weights, they are in sense free as soon as both nodes it connects are selected. I made an example with the key nodes marked in red and the solution (I think) in green.

enter image description here

Edit: While I thought this might reduce to an MST I'm thinking it might actually be a steiner tree problem and therefore NP-hard. The use-case is for a video game, so a fast (and simple) approximate solution is much preferred.

Improve this question
9
  • If you had the distances between each pair of mandatory nodes, you'd be able to use those to find the MST... Commented Jun 2, 2024 at 14:09
  • 1
    @beaker this doesn't work I think you can make counter examples Commented Jun 2, 2024 at 14:24
  • 1
    Ah, yes, you'd need the shortest paths between all nodes so that if an optional node ends up in the MST, you don't accidentally take a longer path to the next mandatory node. Commented Jun 2, 2024 at 14:34
  • A standard greedy algorithm will give you a reasonable first solution. Like so: Find minimum spanning tree of all nodes with every node weight 1. Iterate over optional nodes in order of decreasing weight, check if it can be skipped. In your example, first try node with weight 70 and find it can be removed. Continue with reduced graph. When you reach the node with weight 20, you will find it cannot be removed because you lose connection with the red node at the top of the figure. Commented Jun 2, 2024 at 15:14
  • A more sophisticated approach: Iterate over optional nodes in order of decreasing weight. If the code can be removed without splitting the graph into two ( or more ) components, remove it. When iteration complete find MST of remaining graph. Commented Jun 2, 2024 at 15:24

1 Answer 1

Reset to default
0

This is a special case of the maximum-weight connected subgraph problem. It's NP-hard, but can in practice be solved efficiently even for graphs with tens of thousands of nodes. Best software to solve it: https://scipjack.zib.de/ (disclaimer, I'm one of the developers)

Improve this answer
Sign up to request clarification or add additional context in comments.

3 Comments

Why do you disclaim your own software?
was meant in the sense of "warning"
Hmm, ok, then I guess it's somewhat appropriate, though still odd. (I had suspected you meant "disclosure", as that's what saying "I'm one of the developers" is, but that has nothing to do with warning.)

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.