TIFR CSE 2013 | Part B | Question: 5

Question

Given a weighted directed graph with $n$ vertices where edge weights are integers (positive, zero, or negative), determining whether there are paths of arbitrarily large weight can be performed in time

• A. $O(n)$
• B. $O(n . \log(n))$ but not $O (n)$
• C. $O(n^{1.5})$ but not $O (n \log n)$
• D. $O(n^{3})$ but not $O(n^{1.5})$
• E. $O(2^{n})$ but not $O(n^{3})$

Comments

Useful read 

https://en.wikipedia.org/wiki/Longest_path_problem#Acyclic_graphs_and_critical_paths

---

I think arbitrarily large means that we have to find a path and it can be arbitrarily large, i.e we have to find if any path exists between each pair of vertices. So, the problem is to find whether the graph is connected or not.

---

@smsubham

According to this link , as it is not mentioned that graph is acyclic (i.e. DAG) , so its NP HArd , and can not be solved in polynomial time . so ans should be E.

"

the longest path problem is NP-hard, meaning that it cannot be solved in polynomial time for arbitrary graphs unless P = NP. Stronger hardness results are also known showing that it is difficult to approximate. However, it has a linear time solution for directed acyclic graphs, which has important applications in finding the critical path in scheduling problems"

Src https://en.wikipedia.org/wiki/Longest_path_problem#Acyclic_graphs_and_critical_paths

Answer 1

I think arbitrary large weights means having positive weight cycle.

So, Bellman Ford algorithm can be used.

$O(VE)$

Changing sign of weights of edges.

Correct Answer: $D$

Comments

@Bad_Doctor

O(n!) != O(nlogn)

O(logn!) = O(nlogn)

---

If we are applying Dijkstra algorithm we will create max heap resulting in big oh(E) + we will perform edge relaxation with maximization constraint  but if there are positive edge cycle then this will work other wise we have to apply bellman ford  for Dijkstra algorithm should not time complexity be big oh(n  square log n)  if we are assuming no negative edge cycle is there

---

“out of all paths we output the maximum one “

Answer 2

Some additional information ->

In graph theory and theoretical computer science, the longest path problem is the problem of finding a simple path of maximum length in a given graph. A path is called simple if it does not have any repeated vertices; the length of a path may either be measured by its number of edges, or (in weighted graphs) by the sum of the weights of its edges.

The longest path problem is NP-hard.

However, it has a linear time solution for directed acyclic graphs, which has important applications in finding the critical path in scheduling problems. But graph is acyclic it is not given.

---

First of all thanks to @VS ji for correcting me. Now, Determining whether there are paths(nothing is mentioned what kind of path is this) of arbitrarily large could be done in polynomial time. For any graph  we have two cases -

(1) Graph contains cycle -> In this case  Bellman-Ford  could be used because we have to just check existence cycle. 

(2) Graph does not contains cycle -> Linear time algorithm exists for this case also (as mentioned above).

So best possible Answer in provided option is (D) Part.

---

For more information please refer  - https://en.wikipedia.org/wiki/Longest_path_problem

Comments

Hi @ashutoshaay26 ji, Please check now. 

---

Hello VS

hope i didn't misinterpret but if you're saying that even if there in graph exist some +ve edge weight cycle , then still Bellman-ford will work then i'm doubtful about this.

If graph contains +ve edge weight cycle and when we convert it into -ve edge weight cycle(converting +w to -w) then bellman ford will fail to calculate shortest path.

---

@Rupendra Choudhary,

If Bellman ford fails in the negated Graph that means that there is a positive cycle in the original graph which can give us arbitrarily large distances b/w 2 vertices..isn't it?

And as VS mentioned, the path might not be simple so a vertex involved in a cycle can be visited after arbitrary no. of loops (like case 4 shown by VS) 

Answer 3

arbitrary: based on random choice or personal whim, rather than any reason or system.

Using this description for 'arbitrary' I would say this problem is asking "If there is a path of weight k" and hence it boils down to subset sum problem.