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.