Algorithms and Complexity Homework #3 Solution

Note this homework is slightly shorter  than  the last two and has an earlier deadline.

 

 

1    Manually run the topological sort algorithm

 

Run the DFS-based  topological sort algorithm  taught in class (not  the algorithm  given in the text- book, which removes an in-degree zero node each time)  using the  example given in Figure  3.8 part (a)  (page  103) of the  textbook  (for your  convenience,  also provided  here; ignore the  shades  of the nodes).   When  performing  DFS,  when  there  are  multiple  choices, use the  alphabetical order.   For example,  you should begin with v1  (the  alphabetically smallest).   From  v1, you should first visit v4. Note:  you should show the DFS timestamps and the order of the output nodes.

 

 

 

2    Semiconnected graph

 

A directed  graph  G = (V, E)  is semiconnected  if, for all pairs  of vertices  u, v ∈ V , there  is a path from u to v or from v to u.  That is, different  from the  strongly  connected  components  where you can go from u to v and  then  back,  here you only need to either  go from u to v or from v to u but don’t have to get back.  Give an efficient algorithm  to determine  whether  or not G is semiconnected. Prove that your algorithm  is correct and then analyze its running  time.  Note:  to get full credit,  your algorithm  needs to run in O(|V | + |E|) time.

 

 

3    A  distance problem

 

Do problem  3.9 on page 110. For your convenience, here is the problem description.



2
 
Suppose  a n-node  undirected (and  unweighted) graph  G = (V, E)  contains  two  nodes s and  t such that the distance  between  s and t is strictly  greater  than   n .  Show that there  must  exist some node v (different from s and t) such that deleting  v (and  all edges incident to v) from G will destroy all paths  between  s and  t.  In other  words,  the  new graph  by deleting  v from G contains  no path between  s and t. Given an algorithm  with running  time O(m + n) to find such v (m is the number of edges).

Hint:  since this problem  concerns distance  in a unweighted  graph,  this leads naturally to BFS...

 

 

10%  extra credits: paths on  a tree

 

This problem  is for students who are looking for some challenge.

You are given T , a undirected tree  (i.e.  connected  and  acyclic graph).   The  objective  is finding two nodes u, v of T s.t.  the distance  (i.e.  the number  of edges along the unique path  between  u and

v) is the maximum.   Na¨ıvely, you can try  all possible pairs  of nodes but  this is very slow. Here is a very simple algorithm  for this problem that runs in linear time.

You start from any node s as the  source and  perform  BFS.  Let u be the  node with  the  largest distance  from s (i.e.  at  the  largest  level).  Then  you perform  a second BFS: this  time  you use u as the source.  Let v be the node with the largest  distance  from u.

Now, prove this claim:  the distance  between u and v is the largest possible distance  between any two nodes on the tree.