Algorithms and Complexity No.3

Critical edges:

Given:
G=(V,E) be a connected undirected graph. We say an edge (u,v)\in E is critical if removing it disconnects the graph.

Want:
Given an algorithm for identifying all critical edges.

Solve:
Fun DFS on G to get a single tree T.

1. non-tree edges cannot be critical

This is because the tree keeps the graph connected even if all non-tree edges are removed. This reduced the search space for critical edges from m to just n-1.

Let D_u be the set of descendants of u in T, consider u to be a descendant of itself, so u\in D_u. Using the discovery times of DFS define for every vertex u:
\text{low}[u] = min \left\{ \begin{array}{cc} \text{d}[w] & | (x,w)\text{ is a non-tree edge and }x\in D_u\\ \text{d}[u] \end{array} \right.
Recall DFS tree of an undirected graph, all non-tree edges connect 2 nodes such that one is the descendant of the other. So \text{low}[u] captures how high up the tree we can go from u by taking zero or more edges down the tree followed by a single non-tree edge to reach a node w up in the tree.

In order to keep \text{low}[u] well defined (in case that no non-tree edge exists), we also consider the option of staying at u. The discovery time of the vertices decreases as we go up the tree we take the minimum of the discovery times of the vertices before mentioned.

We now claim that a tree edge (u,v), where v is u‘s parent, is a critical edge if and only if \text{low}[u]=\text{d}[u]. The only way to remain connected is through a non-tree edge (x,w) where x\in D_u and w\notin D_u.

In that case, we know that \text{d}[u]>\text{d}[w]\geq \text{low}[u]. Otherwise, if no such edge exists, we have \text{d}[u]=\text{low}[u] and removing (u,v) disconnects the graph.

We could identify all critical vertices in O(n) time if we had these low values.

To pre-compute
\text{earliest-non-tree}[u]=min\{\text{d}[w]|(u,w)\text{ is a non-tree edge}\},

for each vertex u in O(m) time. Then we can compute low by using the following relation:
\text{low}[u]=\min_{x\in D_u}\text{earliest-non-tree}[u],
which would take O(n) for each u.

Thus computing \text{low}[u] for all u \in V would take O(n^2) time.

NOW, to get a more efficient algorithm we need to re-use come computation. This can be done if we re-difine \text{low} recursively:
\text{low}[u]=\min_{x\in D_u}\text{earliest-non-tree}[u], \min_{v:child of u}\text{low}[u]\}.

The two definitions are clearly equivalent, but the second one leads immediately to a O(n) algorithm for computing \text{low}[u] for all u \in V, provided \text{earliest-non-tree}[v] is given for all v \in V.

So this approach takes O(m+n) time.

188 days ago /  Tagged: , 2 2

2 Comments

  1. Kameryn
    December 1, 2011 at 12:20 am · Reply

    Your answer was just what I nedeed. It’s made my day!

    • Marcelo
      February 9, 2012 at 12:54 pm · Reply

      i have poblrem with your algorithm, i have list like
      $this->graph_arr = array();$n = new Node(“15″, array(“36″, “211″));
      array_push($this->graph_arr, $n);$n = new Node(“32″, array(“15″, “199″));
      array_push($this->graph_arr, $n);
      //$n = new Node(“36″, array(“49″,“50″,”32″,”486″,”542″,”328″,”561″,”1141″,”653″,”654″,”512″,”80″,”800″));$n = new Node(“36″, array(“32″,”49″, “80″,”328″,”486″,”512″,”542″,”561″,”653″,”654″,”800″,”1141″));
      array_push($this->graph_arr, $n);//$n = new Node(“49″, array(“1141″, “542″,”36″,”1153″));
      $n = new Node(“49″, array(“36″, “542″,”1141″,”1153″));
      array_push($this->graph_arr, $n);$n = new Node(“328″, array(“49″, “653″));
      array_push($this->graph_arr, $n);
      //$n = new Node(“542″, array(“1141″, “50″));$n = new Node(“542″, array(“50″, “1141″));
      array_push($this->graph_arr, $n);//$n = new Node(“653″, array(“654″, “50″));$n = new Node(“653″, array(“50″, “654″));
      array_push($this->graph_arr, $n);$n = new Node(“800″, array(“801″, “802″));
      array_push($this->graph_arr, $n);i have clalled in main php like$graph = new Graph();echo “”;$graph->printGraph($graph->getGraph());echo “———————————- ”;
      //$graph->getAdjacentNodes();
      //$graph->dfs(@$_GET['s'], @$_GET['f']);
      //$graph->dfs_recursive(@$_GET['s'], @$_GET['f']);
      //$graph->dfs_recursive(36,802);
      //$graph->dfs_recursive(36,50);
      //$graph->dfs_recursive(’36′,’50′);
      //$graph->dfs_recursive(’36′,’653′);$graph->dfs_recursive(32,542);$graph->printDfsSolution();

      but in line $finish_node_name = $this->getNode($finish_node_name);

      i bekomme empty $finish_node_name

      why!!

Leave a Comment