Hello!

Can I get some help with the following question of Computation and Complexity?

You can do any 2 of the 3 questions.

Thank you in advance!!

Please try the following questions for next week: 1. A simple path in a directed graph is a path that does not repeat any nodes. Let SPATH = {(G'j S, ta k)| G contains a simple path of length at most k from s to 15}. Show that SPATH E P, i.e. describe a polynomial time algorithm deciding SPATH (rst describe your algorithm step by step, and second show that on any graph with n nodes, your algorithm takes at most 0(nk) steps for some integer k). (Hint: be inspired by the colouring algorithm seen in the tutorial for PATH). 2. A graph is connected if every two nodes have a path between them. Let CONNECTED = {(G)| G\" is a connected graph}. Show that CONNECTED E P. (Hint: use the algorithm for PATH as a subroutine). 3. A triangle in an undirected graph is a set of 3 nodes, wherein every two nodes are connected by an edge. Let TRIANGLE = {(G)| G contains a triangle}. Show that TRIANGLE E P, i.e. describe a polynomial time algorithm deciding TRIANGLE. n . u