What is the time complexity of Bellman-Ford single-source shortest path algorithm on a complete graph of n vertices?
In a complete graph total no of edges is
Time complexity of Bellman-Ford algo for a graph having n vertices and m edges = O(nm) for a complete graph time complexity
The Ackermann’s function
Ackermann’s function has exponential time complexity,
Which of the following statements are TRUE?
1. The problem of determining whether there exists a cycle in an undirected graph is in P.
2. The problem of determining whether there , exists a cycle in an undirected graph is in NP.
3. If a problem A is NP-Complete, there exists a non-deterministic polynomial time algorithm to solve A
1. By depth first search we can find whether there exits a cycle in an undirected graph in O(n2) times so it is P problem.
2. As so this problem will also be considered as NP problem.
3. This is the definition of NP-complete so it is trivially true.
Consider two decision problems Q1, Q2 such that Q1 reduces in polynomial time to 3-SAT and 3-SAT reduces in polynomial time to Q2. Then which one of the following is consistent with the above statement?
Given Q1 ≤ 3-SAT and 3-SAT ≤ Q2 3-SAT is NP- complete.
∴ It is NP as well as NP-hard.
is NP-problem 3-SAT ≤ Q2 and 3-SAT is NP-hard ⇒ Q2 is NP- hard problem.
So the strongest statements is Q1 is in NP and Q2 is NP-hard.
Language L1 is polynomial time reducible to language L2. Language L3 is polynomial time reducible to L2, which in turn is polynomial time reducible to language L4. Which of the following is/are True?
I. If L4 ∈ P , L2 ∈ P
II If L, ∈ P or L3e P, then L2∈ P
III. L, ∈ P, if and only if L3∈ P
IV. If L4 ∈ P, then L1 ∈ P and L3 ∈ P
if L1 ∈ P we cannot say anything about L2 from
Since we cannot say anything about L2 therefore we cannot say anything about L3 either from
So Statement III is false.
IV. If L4∈ P, then L1 ∈ P and L3 ∈ P is true.
If L4 ∈ P then fromwe can get that L2∈ P.
and from we can now get that L3 ∈ P
also from we can get that L1 ∈ P
So Statement IV is true.