4

I'm facing an undirected weighted graph problem that I'm sure has been tackled many times, and I'm wondering if it has a name and existing algorithm. Edges represent value I want to capture and maximize, starting from a subgrid and expanding outward until it's not worth it any more to continue.

Let's say my starting grid is composed of nodes 3 and 5 in the image below. I want to capture the big numbered edges and avoid the small numbered edges. The best greedy move would be to 4 to capture the large 15 edge, now my grid is 3, 5 and 4. The next best move would be connecting 5 to 8 to capture the 12 edge.

Graph

Now, a greedy algorithm might not connect that huge 20 connection, since it requires a weaker move like 4 to 7 or 2 to 1 first. Could I use something like an A* or Dijkstra's? And as for a stopping point how do I capture the "cost" of expansion? Do I just calculate the length of the segments traveled and compare it to the edge value captured and subtract it from the segment's value?

Ben Hendel
  • 51
  • 4
  • Can't see the image, sounds similar to prize-collecting TSP from your description. There are many prize-collection variants of NP-hard optimization problems, so "prize-collecting" is a reasonable keyword for searching the theory literature. – David Eisenstat Aug 23 '22 at 16:55
  • Fixed. There is no path or traversal order in this case, just a grid expanding until not cost effective. I will look for prize collecting – Ben Hendel Aug 23 '22 at 17:24
  • 1
    It isn't clear what exactly you are trying to maximize. If it's the total value on edges, then why not just expand to all edges? – n. m. could be an AI Aug 23 '22 at 17:46
  • 1
    Ah, more similar to prize-collecting Steiner tree then, but with edge weights instead of node weights. I think we can reduce to p-c Steiner by subdividing each edge and assigning its prize to the new node. – David Eisenstat Aug 23 '22 at 18:44
  • "And as for a stopping point how do I capture the "cost" of expansion? Do I just calculate the length of the segments traveled and compare it to the edge value captured and subtract it from the segment's value" You might, do that, but then instead of capturing all edges, just capture those with positive `prize - cost` values. Still not very complicated. – n. m. could be an AI Aug 23 '22 at 19:23
  • 1
    @n.1.8e9-where's-my-sharem. That wouldn't work since I might want to take a negative edge at a loss to get to a high value prize edge – Ben Hendel Aug 23 '22 at 19:25
  • 1) Replace your graph G by its [line-graph](https://en.wikipedia.org/wiki/Line_graph) L: every edge of G corresponds to a node in L, and two nodes in L have an edge iff the corresponding edges in G are incident. 2) Solve the [Maximum-Weight Connected Subgraph](https://math.stackexchange.com/questions/1824344/maximum-edgeweight-connected-subgraph-of-an-undirected-graph) problem in graph L. 3) Done. – Stef Aug 23 '22 at 20:09

0 Answers0