Eliminate edges in a routing graph which aren't used in the shortest path between a subset of nodes

Question

I have a large undirected rail routing graph with millions of nodes, which each have a low number of neighbours. I use the graph for routing between a few thousand terminals and I would like to reduce the memory required by the graph, without affecting the shortest paths between any of the terminals. I know that a lot of the edges in the graph won't be on the shortest paths between any pair of those terminals (could be 50%, could be 95%, I don't know).

How can I find and eliminate as many of the useless edges (and/or nodes) as possible but balanced against compute requirements?

I'm interested the perfect solution but I'd prefer something which gets to 90% of the perfect solution with 50% of the resources, for example.

Some ideas I've been considering:

Perfect solution

Use a shortest path algorithm (Dijkstra / A*) to find the shortest paths between each of the pairs, eliminate all edges not used in any of those paths.

It seems like this is will take too much resources and is not worth trying.

Spectral clustering

I've only read a little about this but it seems like it would be off the table due to requiring an adjacency matrix which at |V|^2 would require too much memory.

Remove nodes with a single edge

Any node which is not one of the terminals and only has one neighbour can be removed, repeating this process does remove a chunk, but I know there is much more.

Find bridges and cut if not needed

I could use Tarjan's algoithm to find bridges, each bridge connects 2 subgraphs. If one of the subgraphs has no terminal, it can be removed. If it has only a few terminals, I could use the perfect solution above within it (and to the bridge itself).

I haven't tried this but I think it would be quite effective, but there will still be large highly connected parts of the grpah with 2 or 3 connections to the rest of the graph which can't get compressed by this method.

Extend that to doubly-bridged subgraphs

I have read somewhere that Tarjan's algorithm can be modified to detect subgraphs with only 2 edges to the the rest of the graph - it seems intuitive that it could work but I don't have the full picture of how that works.

Answer 1

You do not exactly say, but I assume you want to do this so that routine questions about the route between two of the terminals can be made super efficient.

So, here is how I would tackle it.

0.  Remove leaf nodes ( nodes with a single edge )
1.  Contruct initial data structure containing
1.1     Graph Eq
1.2     Set of terminal pairs St
1.3     Flag Built.  Set Built = FALSE
2.  A query comes in for the shortest path between two terminals 
3.  IF BUILT == true
3.1      Find shortest path between terminals in Eg
3.2      LOOP back to 2
4.  Find shortest path between terminals in Fg
5   While waiting for next query
5.1     Add terminals to St
5.2     Add shortest path ONLY to Eg
6.  A new query comes in for path between two terminals
7.  IF terminals pair in St find path in Eg
8.  ELSE
8.1     Find shortest path between terminals in Fg
8.1     Add terminals to St
8.2     Add shortest path ONLY to Eg
8.4     IF all terminal pairs in St set Built to TRUE   
10.  LOOP back to 2.