DESIGN AND ANALYSIS OF ALGORITHMS 

ASSIGNMENT NO.3   
Group Members: 

CED18I065 Animesh Kumar  

CED18I017 Dhruv Sawarkar   
CED18I022 Haldhar Dwivedi  
CED18I064 T Karthikeyan  
CED18I011 Vamsi Rajan B  
CED18I012 Rudra Chogale  
CED18I048 Shah Anwaar Khalid  

1. What is the complexity of checking whether a given graph is triangle-free.

Present an algorithm and its analysis.

Sol)
We can use DFS( or BFS) to check whether a graph contains a triangle or not. (
We can also use the same algorithm to list all triangles and count no. of triangles
in the given graph).
Pseudo Code for the algorithm:

STEP 1: Constructing DFS Tree

//Recursive DFS

Void DFS ( Graph G, Vertex v)

{
Visit[v] = 1; //visit the given vertex

For each adjacent unvisited neighbor x of v

DFS_Tree[v][x] = 1 && DFS_Tree[x][v] =1;
DFS(G,x)
}

STEP TWO: Finding missing edges in DFS_Tree

For each 1 entry in the adjacency matrix of graph G, check the corresponding
entry in DFS_Tree.

If corresponding entry is 0( the pair(x,y) form a missing edge)

STEP 3: for every missing edge(x,y) in G, check if they have a common

neighbour

{
Loop from i=0 to i=n
Check if ( G[x][i] && G[y][i] ==1 //ie x,y have a common neighbour)
Return true;
}
Complexity Analysis:

Recursive DFS = O(n+m)

Module 2= O(n^2) //looping through adjacency matrix
Module 3= O(mn)

Total = O(n+m) + O(n^2) + O(mn)

= O(n^3) (m = n^2)
2. How do you use BFS as a black box to find single-source shortest paths
(shortest paths from a fixed vertex to other vertices) in weighted graphs. Analyze
the complexity of your algorithm in terms of the input size.

Sol)

Pseudo Code:

Step 1: Construct BFS_Tree

Void BFS( Graph G, Vertex v)

{
visit[v]= 1;

For each adjacent unvisited node x of v

Visit[x] =1 ;
Enqueue[x];

while(queue is non empty)

int x = dequeue();
For each adjacent unvisited node y of x
Visit[y] = 1;
enqueue[y];
}

Step 2: Shortest path using BFS_Tree

Int spath ( Vertex v, vertex x)

{
if( v==x)
return 0;
Else if ( directpath(v,x) exists) //check if BFS_Tree[v][x]==1
Return 1;
Else
Find neighbour y of x
Return (spath(v,y) +1);
}
Complexity Analysis:
Module 1: BFS-> O(n+m)
Module 2:
spath(v,x) = spath(v,y) + 1
= spath(v,v’) + O(n) ( worst case is a single side tree)
= 1+ O(n)
=O(n)

Total = O(n+m) + O(n)

= O(n+m)

3. Principle of optimality: any subpath of a shortest path is shortest. Show

that the principle of optimality is not always true for longest paths. That is,
subpaths of a longest path need not longest paths. Present a counter
example.
Solution:

Statement(a): Any subpath of a longest path is always longest.

The above statement can be proved (i.e “Subpath of a longest path need not be the longest
path”) with the below example.
Note: Lpath(u,v)={(u1,u2), (u2,u3), (u3,u4), .., (v’,v)} is longest path between vertices u and v
Where the ordered set is are the edges followed.
For above graph G

Lpath(0,5) = {(0,1), (1,2), (2,3), (3,4), (4,5)}

Below is the Lpath(0, 5):

Lets focus on the subpath { 0, 1 } whose length is 1 unit.

The Lpath( 0, 1) will be:

Lpath(0,1) = {(1,2), (2,3), (3,4), (4,5), (5,0)}

Below is the Lpath(0, 1) ​p:​

But the Lpath(0, 1) has a length of 5 units.

Thus the Lpath(0, 1) is a counterexample of the Statement(a), where there exists

a longer path ​p​ between 0 and 1 , than the path considered while calculating the
Lpath from 0 to 5.

4. How do you use BFS as a black box to test whether a given graph is
3-colorable or not (minimum number of colors to color the graph is 3).
Present an algorithm and its analysis.

Solution:
Every vertex will have three containers
Each of the containers can be filled or occupied. Container i being filled with X
means vertex is colored using color i. Container i being filled with 0 means vertex
cannot be colored using color i.
Preference while filling the container :
Container 1 > container 2 > container 3
We will list down the vertices in non-increasing order of degree.
For every vertex in the graph(traversing in order mentioned above)
Corresponding container will be filled with X based on the preference
keeping in mind the container is not occupied.
if( all containers are occupied) //case 2
print “ graph is four colorable or more “
exit;
All the neighbours will be filled with 0.
After all the vertices are colored
If there exists a container which is not filled in any of the vertices. //case1.1
print ‘ graph is two colorable or less than”
Else //case 1.2
Print “ graph is three colorable “

EXAMPLES

All columns have x. Therefore, the graph is 3 colorable.

Dth column has all 0’s. Therefore, the graph is not 3 colorable.

All columns have X. Therefore , the graph is 3 colorable.

Time complexity
O(V^2) for finding the degree of every vertex in graph
O(VlogV) for sorting the vertices based on their degree
For loop : O(E) ( each edge will be visited at most twice->O(2E)= O(E))
That is O(E) for coloring ( filling the container) all the vertices
O(V) for checking tricolorability
Total : O(V^2 + VlogV + E + V) = O (V^2 + E)
5. Which are the data structures used to implement (i) BFS (ii) DFS.
Sol) BFS= Queue
DFS= Stack

6. Show that slanting and cross edges do not exist in DFS, and back edges
do not exist in BFS.

Sol)
Claim: Slant and cross edges do not exist in DFS.
Direct Proof:
Claim:In DFS, missing edges are only allowed between vertices of the same
branch.
Proof: Consider the DFS_tree below. Assume there’s a back edge b/w C and E.
However this can never happen because when algorithm backtracks to E, it will
visit C. And therefore , C is visited through E before it would've been visited
through A.
Claim: Back Edges do not exist in BFS.
Direct Proof:
Claim: In BFS, missing edges are only allowed between different branches.
Proof: Consider the BFS_tree below. Assume there’s a missing edge b/w C and
E. However, this can never happen because when the algo is at C, it will visit all
the neighbours of C first before moving to the next level. Therefore, E is visited
through C and there cannot exist a missing edge b/w them.
7. How do you find the shortest cycle in an unweighted graph? Present an
efficient algorithm along with its analysis.

Sol)

Pseudocode:
Int min = infinity;
Run BFS to get BFS_tree. Put all missing edges into a set S.
For​ every edge e(u,v) in set S,
check if​ G-e contains a path b/w (u,v).
If yes, using BFS find spath b/w u and v.
Length of cycle = spath +1;
Update min if current cycle length is smaller.
Return min;
End.

Analysis:
m = |E(G)|, n = |V(G)|
(Edges) O(m-n+1) x O(m+n) ( using BFS to find spath)
= O(m^2) = O(n^4)

8. Present a greedy algorithm to find the longest cycle in an unweighted graph.

max= -infinity;
Tree TR; //required tree
Int LR; //required length
For every vertex V belonging to graph G
Tree T=DFS(V); //DFS(V) will return the dfs tree formed keeping V as
source vertex
For every missing edge (u,v)
L =( level difference b/w u and v) + 1;
If ( L > max)
LR = L;
TR = T;
Vertices b/w u and v in TR along with the edge (u,v) will be the required
longest cycle and its length LR.
9. Show that ’max-degree’ greedy and ’edge-coloring’ greedy do not give
optimum for policemen problems.

Consider the following variant of Edge coloring approach:

For each edge we will store which vertex policeman is covering it.
In the end, look at all the vertices where a policeman is placed. If for a vertex, all
incident edges are covered by 2 policemen, remove the policeman from that
vertex.

Consider the following trace of above algorithm:

10. SECOND-BEST-MST: a spanning tree T 0 whose weight W(T 0 ) = min{W(T
00) | T 00 is a ST and T 00 is not a MST}. Present an algorithm with a tight
analysis to compute second best MST.

Sol)

The algorithm for calculating Second Best MST is based on the following
observations:
● As part of MST, for every cycle we exclude the edge having maximum
weight.
● Therefore, for the second best MST, we must compare the cost of
replacing edges currently in MST with the missing edge for every cycle and
choose min.
● We shall choose the minimum cost of replacement as part of our spanning
tree, rest everything is the same.

Pseudo Code :
Computations Steps involved in the algorithm:
● Step 1:
○ Construct MST using your favorite algorithm(Prim’s algorithm).
O((m+n)*logn)
○ And initialize min_edge = NIL and min_cost = infinity. O(1)
● Step 2:
○ Find all excluded edges in MST ( i.e : E(G) - E(MST)). (O( n2 ))
○ Find cost of replacing max edge of cycle with excluded edge for all
excluded edges and store it if lesser than min_cost.
(O(m+n))*O(m-n) ( check cycle, missing edges)
● Step 3:
○ Find which cycle min_edge ‘e’ belongs to & replace it with 2nd max
edge in that cycle. (O(m+n))
T(n) = O((m+n)*logn) + O(1) + O(m+n)*O(m-n) + O(m+n)
T(n) = O( m2 )
T(n) = O( n4 )

Note: Since the defn says the weight of second best MST must be strictly greater
than that of MST, it may not be possible to find second best MST in some cases(
e.g when Graph is a tree).

11. Consider a weighted graph with all edge weights distinct. Is MST unique. How
about the second best MST.
Sol) (i)MST will be unique.
Proof:
Notations:
G is input graph
V and E are sets of vertices and edges of G respectively.
S and S’ are subsets of E
If T = (V, S) and T' = (V, S') are two distinct MSTs for G, let e = (x,y) be the
cheapest edge of G that is in one of T or T', but not both. (Since all the edge
weights are distinct, there is a unique cheapest edge with this property.) Assume
e is in T. Since e is not an edge in T’, to maintain minimal cost w(e) ≥ w(f) for
every edge f on the path in T' from x to y. But since edge weights are distinct,
w(e) > w(f). By the way e was chosen
(i.e cheapest edge only in one of the two graphs), every edge on the path in T'
from x to y also lies in T. But these edges of T, plus the edge e of T, form a cycle,
contrary to T being a tree.
Hence, T’ and T can not be distinct.
(ii)Second best MST, if it exists, is not necessarily unique.
Example:

Second best MST:

(a)

(b)
12.Suppose there are negative edges incident on the source vertex and no
negative edges in other parts of the graph. Will Dijkstra work fine.
Solution:

DIJKSTRA( G, w, s)
1 s.d = 0
2 for all v belongs to​ V(G) - {s} , v.d = ​∞
3 Create an Empty set S
4 Create a MIN-priority queue out of all v belongs to​ V(G)
5 ​while​ Q is not EMPTY:
6 u = EXTRACT-MIN (Q)
7 S = S UNION {u} //u is closed by the Dijkstra
8 for​ every vertex v adjacent to u:
9 if you find a cheaper path to v via u,​ then update the
10 ​ v.d attribute with the new value u.d + w(u, v)

The ​d​ attribute of a vertex ​v​, holds the minimum estimate of the path length
from the source ​s​ to ​v​.
Let's take the below case, 0 < n3 < n2 < n1

skipping the steps and jumping to step 6.

Since, the s node has the least value in ​.d​ attribute it will be extracted from
the Q and placed in S(step 7) and Dijkstra will never look at it again.
(​s is closed​).For loop 8-10 updates the ​a.d​ and ​b.d​ attributes accordingly.

In this iteration of while loop the ​a​ node will be extracted from Q and now a
is closed.

Since
1. All the edge incidents on the source node ​s​ are bound to have higher
weight than the wait(​s​, a
​ ​).
2. All the edges incident on a are bound to have positive weights.
There can not be a case when we have to look for updating the .d attribute
of a. Thus Dijkstra’s algorithm works well here even though we are having
negative weighted edges just because here the case of re-updation of an
already closed node(the node which has been dequeued and inserted in
set S) does not occur. So,​ Yes! Dijkstra’s Algorithm works fine.

13. Consider a vertex weighted graph (no weights on edges, vertex weighted
instead) with a fixed source. How do you use Dijkstra as a black box to find
shortest paths from a fixed source?
Solution:
(i)Undirected graph
For all edges (u,v) replace them with directed edges (u,v) and (v,u)
Weight(u,v)=Weight(v)
Weight(v,u)=Weight(u)

(ii)Directed graph
For all edges (u,v), Weight(u,v)=Weight(v)

After doing all the above steps use Dijkstra to find shortest paths from a
fixed source in terms of edges
Then replace those (u,v) edges with node v
This will give the shortest paths from a fixed point in terms of vertices.
14. Show that if a graph is acyclic and has n − 1 edges, then the graph is
connected.
15. Present a linear time algorithm to compute the longest path in a tree.

Sol)
The algorithm is based on the following observations:
1. Longest path will exist between two leaf nodes.
2. Let (u,v) be the end points of the longest path:
● For any vertex x of the tree, max distance vertex will be either
u or v.
From observation 2, we can deduce the following algorithm:
(i) Run BFS wrt to an arbitrary vertex to find either u or v.
(ii) Run BFS wrt to u (or v) to find v (or u).

Complexity : 2*Complexity of BFS= 2* O(m+n) = O (m+n)

16. Suppose, we run Prim’s algorithm from a vertex s. Does the tree output by
Prim’s algorithm give the shortest path from s to all other vertices.
Solution:
No, both of them are not the same.
A graph formed from all spaths from vertex s can have a total cost of graph
higher than the MST
This is because any MST sacrifices spath in favour of total lower cost of tree

Graph Cost: (0,1) =2, (0,2) =5, (1,2) =4

Resultant of Prim’s algorithm for vertex (0)
Resultant of all spaths from vertex (0)

17. Which are the data structures used to implement (i) Prim’s MST (ii) Kruskal’s
MST (iii) Dijkstra’s SPATH
Solution:
(i) Prim’s MST : Priority Queue with edge cost as key
(ii) Kruskal’s MST : Disjoint set
(iii) Dijkstra’s SPATH :

18. Given an unweighted graph, present two different greedy algorithms to

find (i) a spanning tree with maximum number of leaves (ii) a spanning tree
with minimum number of leaves.
Solution:
Method 1:
(i) ST with max leaves
Pseudo code:
Step 1: For input graph G calculate the degree of all vertices
Step 2: Choose vertex with highest degree (u) and form graph G’
Step 3: For all vertices in the neighbourhood of u include them in G’ and exclude
all edges between vertices of G’ from G
Step 4: Recalculate degree of all leaf nodes in G’ using G and pick max degree
vertex as u
Step 5: Repeat step 3 to 4 till all vertices are visited

GREEDY CHOICE: At every iteration a local maximum degree vertex is

chosen.

(ii) ST with minimum leaves

Pseudo code:
Step 1: For input graph G calculate the degree of all vertices
Step 2: Choose vertex with least degree (u) and form graph G’
Step 3: For all vertices in the neighbourhood of u include them in G’ and exclude
all edges between vertices of G’ from G
Step 4: Recalculate degree of all leaf nodes in G’ using G and pick min degree>0
vertex as u
Step 5: Repeat step 3 to 4 till all vertices are visited
Method 2:
(i) spanning tree with minimum number of leaves
Pseudocode:
for every vertex v belonging to graph G
{
int min,m;
m=DFS(v); // DFS(v) will return the number of leaves in DFS tree
keeping v as source vertex
if(m<min)
min=m;
return min;
}
(ii) spanning tree with maximum number of leaves
Pseudocode:
for every vertex v belonging to graph G
{
int max,m;
m=BFS(v); // BFS(v) will return the number of leaves in BFS tree keeping v
as source vertex
if(m>max)
max=m;
return max;
}