# Identifying useless edges for shortest path

Consider a graph $G$ (the problem makes sense both for directed and undirected graphs). Call $M_G$ the matrix of distances of $G$: $M_G[i, j]$ is the shortest path distance from vertex $i$ to vertex $j$ in $G$ for a certain fixed aggregation function (for instance $+$ or $\max$).

I say that a subgraph $G'$ of $G$ (with same vertex set) is sp-equivalent to $G$ if $M_G = M_{G'}$. In other words, removing edges to go from $G$ to $G'$ does not change the length of shortest paths; the removed edges are not required for any shortest path.

In general there is no single sp-equivalent subgraph of $G$ that is minimal for inclusion. For instance, if $G$ is undirected and all edges have weight $0$, any spanning tree of $G$ is a minimal sp-equivalent subgraph (indeed, any edge in a cycle could be removed, but disconnecting a vertex pair obviously changes the distance). However I can still call edges of $G$ useless if they are in no minimal sp-equivalent subgraph, necessary if they are in all minimal sp-equivalent subgraphs (i.e., in their intersection), and optional if they are in some of them (i.e., in their union).

My first question is: Do these notions have a standard name?

My second question is: What is the complexity of classifying the edges of $G$ in this fashion, depending on whether $G$ is undirected or directed, and on the aggregation function?

(For instance, for $G$ undirected and for $\max$, the minimal sp-equivalent subgraphs are spanning trees of minimum weight, so at least if all edge weights are different the classification is easily computed by computing the unique minimum spanning tree, but in general I do not know how things work.)

• "For instance, if G is undirected and unweighted, any spanning tree of G is a minimal sp-equivalent subgraph." This does not seem to be true: in $K_n$ all distances are $1$, but no spanning tree of $K_n$ has this property. In fact, no subgraph does. Othewise this sound like a spanner en.wikipedia.org/wiki/Graph_spanner#Distance Commented Jun 17, 2014 at 23:28
• In fact, for any undirected unweighted graph $G$, no sp-equivalent subgraph exists: if a subgraph $G'$ does not include edge $(u, v)$, then $1 = M_G[u, v] < M_{G'}[u, v]$. Commented Jun 17, 2014 at 23:34
• I think we can at least say identification is as easy as all-pairs shortest-path: If there is an edge $(u,v)$ but the shortest path from $u$ to $v$ is shorter than that edge, then the edge is "useless" (we should always utilize that shorter path instead of this edge, in any scenario); conversely, if an edge is "useless", then there must be a shorter path than that edge length from $u$ to $v$. So just iterate over edges and check if there is a shorter path than that edge. (The above is for usual shortest-path, haven't thought about the $\max$ aggregation rule.)
– usul
Commented Jun 18, 2014 at 0:59
• You might want to look up "distance preservers" Commented Jun 18, 2014 at 4:38
• Sasho Nikolov: Sorry, for undirected and unweighted graphs, I meant edges of weight 0, not 1. Rephrasing this in the question.
– a3nm
Commented Jun 18, 2014 at 6:37