edited by
1,198 views
4 votes
4 votes

Consider the following statements:

  1. Checking if a given $undirected$ graph has a cycle is in $\mathsf{P}$
  2. Checking if a given $undirected$ graph has a cycle is in $\mathsf{NP}$
  3. Checking if a given $directed$ graph has a cycle is in $\mathsf{P}$
  4. Checking if a given $directed$ graph has a cycle is in $\mathsf{NP}$

Which of the above statements is/are TRUE? Choose from the following options.

  1. Only i and ii
  2. Only ii and iv
  3. Only ii, iii, and iv
  4. Only i, ii and iv
  5. All of them
edited by

1 Answer

Best answer
11 votes
11 votes

E. All of them. Because all of them can be solved by Depth first traversal.

Every P problem is a subset of NP.

edited by
Answer:

Related questions