TIFR CSE 2025 | Part B | Question: 5

Question

Given a directed graph $G$ and an initial vertex $s$, we would like to $explore$ the graph from $s$, that is, starting from $s$ see all vertices along a path.

For example, the graph on the left side below cannot be explored from $s$ since there does not exist a path along which we can visit all vertices starting from $s$ while the graph on the right side can be explored from $s$ by following the path $s \rightarrow u \rightarrow s \rightarrow t$.

Which of the following is TRUE?

• A. There exists a polynomial time algorithm to explore the graph from $s$.
• B. There exist s an exponential time algorithm to explore the graph from $s$ but there does not exist any polynomial time algorithm.
• C. There exists an algorithm to explore the graph from $s$ but it is not known if it runs in exponential time.
• D. The decidability of the problem is open.
• E. The halting problem of Turing machine can be reduced to checking if a graph can be explored from $s$.

Answer 1

The Halting problem can be reduced…” — Whenever you see this, be suspicious.
This usually hints at undecidable problems, but reachability in graphs is decidable in P

Reachability in directed graphs → solved by DFS or BFS in O(V+E)
 So the answer must be:

Checking Reachability

Always solvable in polynomial time

 

There exists a polynomial time algorithm to explore the graph from s