Prove that each of following problems is in P by sketching a polynomial time alg

Question

Prove that each of following problems is in P by sketching a polynomial time algorithm that solves it. Briefly justify that your algorithm runs in polynomial.
(4) SPATH = {G,s,t,k | G is an undirected graph with a simple path from s to t with length at most k} Prove that each of following problems is in P by sketching a polynomial time algorithm that solves it. Briefly justify that your algorithm runs in polynomial.
(4) SPATH = {G,s,t,k | G is an undirected graph with a simple path from s to t with length at most k} Prove that each of following problems is in P by sketching a polynomial time algorithm that solves it. Briefly justify that your algorithm runs in polynomial.
(4) SPATH = {G,s,t,k | G is an undirected graph with a simple path from s to t with length at most k}

Explanation / Answer

Hope this might help you to solve your query.

.....................

To show SPATHP, we can construct a TM T which can decideS PATH in polynomial time.
T = ”on input< G, s, t, k >
”
1. Use BFS starting from s , and mark the searched nodes with their depths.
2. If the node t is marked and its depth is less than or equal to k, accept;
otherwise,reject.
(Time complexity:)In the step 1, BFS traverses every node at
most once, so its time
complexity is O(|V|+|E|).
The step 2 to can be finish in one comparison, so T can decide SP AT H in polynomial
time (O(|V|+|E|)). We can conclude SP AT HP.

Related Questions

Navigate

• Browse (All)
• Browse P
• Subjects

---

---

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.