<p>If you are looking for a way to name (or alternately characterize) these edges you call "useless" and "necessary," you could refer to them as the edges with betweenness centrality =0 and =1, respectively. Every edge can be classified as having =0, =1 or in(0,1) betweenness measure in time of all-pairs-shortest-paths.</p>

<p>This is a well-studied measure of network edges, and there are fast algorithms for updating all the edges' centrality scores upon edge deletions (but I'm not sure about other perturbations).</p>

<p>A centrality function is built-in to mostly every network analysis I've seen, and there is a definition that applies to directed graphs as well:</p>

<p>(edit: the link I gave initially only discussed node betweenness centrality, but here is the only wikipedia article I can find that discusses edge-betweenness centrality:
<a href="http://en.wikipedia.org/wiki/Girvan%E2%80%93Newman_algorithm" rel="nofollow">http://en.wikipedia.org/wiki/Girvan%E2%80%93Newman_algorithm</a>
Still, edge-betweenness is a standard measure that can usually be found in network analysis packages.)</p>

CC BY-SA 3.0
2014-07-01T12:48:51.387Z
I think the difference between node betweenness centrality and edge betweenness centrality is inessential because you can always add intermediate nodes to edges, or copy nodes and add one edge from one copy to the other, to reduce one definition to the other. This is a useful pointer, thanks for making me aware of this!
Antoine Amarilli 'a3nm'
CC BY-SA 3.0
2014-06-23T22:24:40.127Z
2014-06-23T22:37:12.317Z
2014-06-23T22:37:12.317Z
JimN
<p>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$).</p>

<p>I say that a subgraph $G'$ of $G$ (with same vertex set) is <em>sp-equivalent</em> 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 <em>required</em> for any shortest path.</p>

<p>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$ <em>useless</em> if they are in no minimal sp-equivalent subgraph, <em>necessary</em> if they are in all minimal sp-equivalent subgraphs (i.e., in their intersection), and <em>optional</em> if they are in some of them (i.e., in their union).</p>

<p>My first question is: <strong>Do these notions have a standard name?</strong></p>

<p>My second question is: <strong>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?</strong></p>

<p>(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.)</p>

CC BY-SA 3.0
2014-06-17T22:30:31.597Z
Related: http://stackoverflow.com/questions/12414843
BlueRaja - Danny Pflughoeft
CC BY-SA 3.0
2014-06-17T23:28:29.120Z
"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 http://en.wikipedia.org/wiki/Graph_spanner#Distance
Sasho Nikolov
CC BY-SA 3.0
2014-06-17T23:34:54.870Z
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]$.
Sasho Nikolov
CC BY-SA 3.0
2014-06-18T00:59:58.120Z
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
CC BY-SA 3.0
2014-06-18T04:38:26.363Z
You might want to look up "distance preservers"
arnab
CC BY-SA 3.0
2014-06-18T06:37:08.753Z
Sasho Nikolov: Sorry, for undirected and unweighted graphs, I meant edges of weight 0, not 1. Rephrasing this in the question.
Antoine Amarilli 'a3nm'
CC BY-SA 3.0
2014-06-18T06:39:15.377Z
arnab: Distance preservers are definitely related but note however that they are not necessarily subsets of the original graph, unlike what happens here.
Antoine Amarilli 'a3nm'
CC BY-SA 3.0
2014-06-18T07:24:41.423Z
Distance preservers are usually defined as subgraphs: http://dl.acm.org/citation.cfm?id=1070524
arnab
<ds.algorithms><reference-request><graph-algorithms><shortest-path>
Identifying useless edges for shortest path
Antoine Amarilli 'a3nm'
# Identifying useless edges for shortest path

(Asked by: username_0 on 2014-06-17)

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.)

**Tags:** ds.algorithms, reference-request, graph-algorithms, shortest-path

> **Comments:**
> **username_1**: Related: http://stackoverflow.com/questions/12414843  
> **username_2**: "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 http://en.wikipedia.org/wiki/Graph_spanner#Distance  
> **username_2**: 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]$.  
> **username_3**: 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.)  
> **username_4**: You might want to look up "distance preservers"  
> **username_0**: username_2: Sorry, for undirected and unweighted graphs, I meant edges of weight 0, not 1. Rephrasing this in the question.  
> **username_0**: username_4: Distance preservers are definitely related but note however that they are not necessarily subsets of the original graph, unlike what happens here.  
> **username_4**: Distance preservers are usually defined as subgraphs: http://dl.acm.org/citation.cfm?id=1070524  

---

## 1 answers

### Answer by username_5 on 2014-06-23. Score: 4

If you are looking for a way to name (or alternately characterize) these edges you call "useless" and "necessary," you could refer to them as the edges with betweenness centrality =0 and =1, respectively. Every edge can be classified as having =0, =1 or in(0,1) betweenness measure in time of all-pairs-shortest-paths.

This is a well-studied measure of network edges, and there are fast algorithms for updating all the edges' centrality scores upon edge deletions (but I'm not sure about other perturbations).

A centrality function is built-in to mostly every network analysis I've seen, and there is a definition that applies to directed graphs as well:

(edit: the link I gave initially only discussed node betweenness centrality, but here is the only wikipedia article I can find that discusses edge-betweenness centrality:
<http://en.wikipedia.org/wiki/Girvan%E2%80%93Newman_algorithm>
Still, edge-betweenness is a standard measure that can usually be found in network analysis packages.)

> **Comments:**
> **username_0**: I think the difference between node betweenness centrality and edge betweenness centrality is inessential because you can always add intermediate nodes to edges, or copy nodes and add one edge from one copy to the other, to reduce one definition to the other. This is a useful pointer, thanks for making me aware of this!  

---

