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

$\endgroup$
  • 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 Jun 17 '14 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 Jun 17 '14 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 Jun 18 '14 at 0:59
  • 3
    $\begingroup$ You might want to look up "distance preservers" $\endgroup$ – arnab Jun 18 '14 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$ – a3nm Jun 18 '14 at 6:37
3
$\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.)

$\endgroup$
  • $\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$ – a3nm Jul 1 '14 at 12:48

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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