Toll placement problem (Graph theory)

I'm working on a problem that reduces to something like toll plaza placement on a set of highways. Given a large undirected graph and a list of node pairs with a toll value between them, I need to find the minimal set of toll plaza nodes that can levy the tolls (each plaza node can levy an arbitrary set of tolls). Each node would have a weight that defined how suitable it is to be a toll plaza. This seems like a common algorithm, but I've never taken graph theory and my searches haven't turned up much. Any pointers on how to solve this would be appreciated! Graph: [A]----[1]-----[2]----[3]------[C] | | | | [B] [D] For example, in this graph, if there are tolls for (A,D) and (B,C), the nodes 1,2,3 would all be equally suitable to levy the tolls, and I could pick one after sorting them by weight. If instead the toll list was: (A,D) = 5 (B,D) = 6 (B,C) = 7 (A,B) = 1 Then [1] is the only single node that could levy all the tolls. Given lists like these, I want to find the set of "optimal" toll locations like this.

May 5, 2025 - 15:00

I'm working on a problem that reduces to something like toll plaza placement on a set of highways. Given a large undirected graph and a list of node pairs with a toll value between them, I need to find the minimal set of toll plaza nodes that can levy the tolls (each plaza node can levy an arbitrary set of tolls). Each node would have a weight that defined how suitable it is to be a toll plaza.

This seems like a common algorithm, but I've never taken graph theory and my searches haven't turned up much. Any pointers on how to solve this would be appreciated!

Graph:

[A]----[1]-----[2]----[3]------[C]
        |              |
        |              |
       [B]            [D]

For example, in this graph, if there are tolls for (A,D) and (B,C), the nodes 1,2,3 would all be equally suitable to levy the tolls, and I could pick one after sorting them by weight. If instead the toll list was:

(A,D) = 5
(B,D) = 6
(B,C) = 7
(A,B) = 1

Then [1] is the only single node that could levy all the tolls. Given lists like these, I want to find the set of "optimal" toll locations like this.