5

A strongly connected digraph is a directed graph in which for each two vertices and , there is a directed path from to and a direct path from to . Let = (, ) be a strongly connected digraph, and let = (, ) ∈ be an edge in the graph. Design an efficient algorithm which decides whether ′ = (, ∖ {}), the graph without the edge is strongly connected. Explain its correctness and analyze its running time.

So what I did is run BFS and sum the labels, once on the original graph from and then again in G' without the edge (again from ) and then : if second sum (in G') < original sum (in G) then the graph isn't strongly connected.

P.S this is a question from my exam which I only got 3/13 points and I'm wondering if i should appeal..

Nicole
  • 85
  • 10
  • What is Label? Is it the weight of edge?? If it is so, then no doubt your algo will give wrong result. – mukesh210 Feb 11 '19 at 15:45
  • the label is the distance from the root – Nicole Feb 11 '19 at 16:38
  • 2
    Well, your proposed algorithm definitely doesn't work. (Why would removing an edge ever *reduce* the cost to get to a node?) – Sneftel Feb 11 '19 at 16:50
  • it wont, but if it does wouldnt that only happen if the graph isnt strongly connected anymore? like if theres no way of reaching that node now then the sum of all the labels would be less than the original -> not connected – Nicole Feb 11 '19 at 18:15
  • If there were no way of reaching the node, then its cost would be infinite, not less. In any case if all you were trying to accomplish is to figure out whether the graph was disconnected after the edge was removed, why would you bother doing BFS on the pre-removal graph? You already know that one would be connected. – Sneftel Feb 14 '19 at 12:32

2 Answers2

3

As Sneftel points out, the distance labels can only increase. If u no longer has a path to v, then I guess v's label will be infinite, so the sum of labels will change from finite to infinite. Yet the sum can increase without the graph losing strong connectivity, e.g.,

u<----->v
 \     /|
  \|  /
    w

where v's label increases from 1 to 2 because of the indirect path through w.

David Eisenstat
  • 64,237
  • 7
  • 60
  • 120
1

Since the graph G is strongly connected, G' is strongly connected if and only if there is a path from u to v (this path would replace the edge e).

You can use any path finding algorithm to solve this problem.

Thomash
  • 6,339
  • 1
  • 30
  • 50