## NP-Complete

Question 1 |

NP-Complete. | |

solvable in polynomial time by reduction to directed graph reachability. | |

solvable in constant time since any input instance is satisfiable. | |

NP-hard, but not NP-complete. |

Question 1 Explanation:

Note: Out of Syllabus.

Question 2 |

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, 2 and 3 | |

1 and 2 only | |

2 and 3 only | |

1 and 3 only |

Question 2 Explanation:

Note: Out of syllabus.

1. Detecting cycle in a graph using DFS takes O(V+E)=O(V

Here, for complete graph E<= V

2. Every P-problem is NP because P subset of NP (P ⊂ NP)

3. NP – complete ∈ NP.

Hence, NP-complete can be solved in non-deterministic polynomial time.

1. Detecting cycle in a graph using DFS takes O(V+E)=O(V

^{2})Here, for complete graph E<= V

^{2}. So, It runs in polynomial time.2. Every P-problem is NP because P subset of NP (P ⊂ NP)

3. NP – complete ∈ NP.

Hence, NP-complete can be solved in non-deterministic polynomial time.

Question 3 |

Which of the following problems is not NP-hard?

Hamiltonian circuit problem | |

The 0/1 Knapsack problem | |

Finding bi-connected components of a graph | |

The graph colouring problem |

Question 3 Explanation:

Note: Out of syllabus.

There are 3 questions to complete.