IIT Kanpur

Question

Maximum spanning tree problem (MaxST) defined for a weighted undirected graph aims to compute the spanning tree of maximum weight. Longest path problem (LongP) in a weighted directed graph aims to compute path of maximum weight from a given source to a given destination. Which of the following statements is correct:

A. MaxST has a polynomial time algorithm, and LongP does not have any polynomial time algorithm till date except for directed acyclic graphs.

B. MaxST as well as LongP problem don’t have any polynomial time algorithm till date. However, for directed acyclic graph, there is a polynomial time algorithm for LongP.

C. MaxST has a polynomial time algorithm; LongP has a polynomial time algorithm except when the graph has a negative cycle.

D. MaxST has a polynomial time algorithm provided there are no negative edge weights, and LongP does not have any polynomial time algorithm till date except for directed acyclic graphs.

Answer 1

Option A is correct

MaxST can be solved in polynomial time.

Just negate the weights of the edges of the graph and apply Kruskal for finding minimum spanning tree.

LongP is a Np complete problem so it takes exponential time dont have any polynomial time except for DAG (directed acyclic graph)

The algo for finding the LongP in DAG is given below.

Let us assume v₀,v₁,.....v_n be n vertices of the dag

Suppose v₀ be the source from where we have to calculate the LongP for the dag

Here we take a queue Q and an array C[n]

Initialise C[i] = - infinity for i>0 and C[0] =0

STEP 1 Enqueue v₀ 

STEP 2 Enqueue all vertices present in the adjacency list of head(Q) which are not queued already

If any vertex v_j is adjacent to head(Q) then C[j] = max ( C[j] , C[head(Q)] + weight of the edge (head(Q),v_j ) )

STEP 3 Dequeue and then go to STEP 2 repeat STEP 2 and STEP 3 until there is no vertex left be queued.

STEP 4 Return max of the array C.

The above algo will take O(V + E) time.