GATE CSE 2013 | Question: 18

Question

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$

• A. $1$, $2$ and $3$    
• B. $1$ and $2$ only    
• C. $2$ and $3$ only    
• D. $1$ and $3$ only

Comments

lets understand some term 

P = the set of problems that are solvable in polynomial time by a Deterministic Turing Machine.

LIKE binary search ,linear search,breadth first search,depth search,chekhing whether cycle exist in a graph(this is algo behind  prims algorithm to find minimum spanning tree to detect  cycle when we add an edge .its time complexty = O(V+E))  

not polonomial time algo example::sum of subset, 3 sat etc

NP = the set of decision problems (answer is either yes or no) that are solvable in nondeterministic polynomial time i.e can be solved in polynomial time by a Nondeterministic Turing Machine.

Nondeterministic Turing Machine(NTM) — a branching machine. If many options for the next step of computation exists this machine can go down all of them at the same time. NTMs are capable of guessing the correct option out of polynomially many options in O(1) time.

Proving that A Problem X is NP-Complete:: it involves 2 steps. First we have to show that the problem belongs to NP and then we have to show it is NP-hard.

 

Step 1 — Showing X ∈ NP. find a nondeterministic algorithm for X.

Step 2 — Showing X is NP-hard. Reduce from a known NP-complete problem to X(like 3 SAT PROBLEM)

Given problem

option A.Cycle detect algo O(V+E)==P(correct it is polynomial)

option B.every P(Deterministic turing machine accepted) is also NP(non detrministc turing machine).(correct)

option C.Any problem comes in NP -complete when it 

         A.(above step1)  havinng a nondeterminstic polynomial time algo exist for that. (So Option C Is Correct)

         B. is  able to reduce that from some known NP complete problem

 

So option A

---

@sushmita @Ayush Upadhyaya NP, P in syllabus? 

---

No

Answer 1

Cycle detection is graph is in $P$ as it can be done using a graph traversal $(O(V+E))$

Ref: http://www.geeksforgeeks.org/detect-cycle-undirected-graph/

If a problem is in $P$ then it is also in $NP$ as $P$ is a subset of $NP$. So, both 1 and 2 are TRUE. 

Statement 3 is also true as $NP-Complete$ requires a problem to be in $NP$ and for any problem in $NP$, we have a non-deterministic polynomial time algorithm. 

So, answer is A) - 1, 2 and 3 are TRUE.  

Comments

Yes, more precisely non deterministic halting TM I guess.

---

to find the total no of cycle in undirected graph then what would be answer?

---

Gurdeep Saini

Then also decidable , as in the $DFS$ tree we can easily figure out how many cycles are present by checking the back-edges.