11
$\begingroup$

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

Improve this question
$\endgroup$
8
  • 2
    $\begingroup$ "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 $\endgroup$
    – Sasho Nikolov
    Commented Jun 17, 2014 at 23:28
  • 5
    $\begingroup$ 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]$. $\endgroup$
    – Sasho Nikolov
    Commented Jun 17, 2014 at 23:34
  • 2
    $\begingroup$ 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.) $\endgroup$
    – usul
    Commented Jun 18, 2014 at 0:59
  • 3
    $\begingroup$ You might want to look up "distance preservers" $\endgroup$
    – arnab
    Commented Jun 18, 2014 at 4:38
  • 2
    $\begingroup$ Sasho Nikolov: Sorry, for undirected and unweighted graphs, I meant edges of weight 0, not 1. Rephrasing this in the question. $\endgroup$
    – Antoine Amarilli 'a3nm'
    Commented Jun 18, 2014 at 6:37

1 Answer 1

Reset to default
4
$\begingroup$

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

Improve this answer
$\endgroup$
1
  • $\begingroup$ 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! $\endgroup$
    – Antoine Amarilli 'a3nm'
    Commented Jul 1, 2014 at 12:48

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.