Question

3. Give an efficient algorithm that takes as input a directed graph G-(V,E) with edges labeled with either 0 or 1, and vertices s and t that ouputs TRUE if and only if there is a path (not necessarily simple) that goes from s to t such that the binary sequence of edges in the path avoids the substring "11" and outputs FALSE otherwise. (For example, the string 10100010 avoids 11 but the string 00101101110 does not avoid 11.) (6 points for correct algorithm description, 5 for correctness proof, and 4 for efficiency and time analysis your algorithm's efficiency will be taken into consideration for this problem.) and 4 for efficiency and time analysis,

Please show your work

Answer 1

Algorithm is very simple. We will perform search analogous to Breadth First search where starting from vertex s we will explore the neighbours with the rule that we will include an edge (u,v) in BFS tree if and only if label of both u and v are not 1. Thus our explore method will explore every vertex v in the graph such that path from vertex s to vertex v will exist in BFS tree if and only if there is no sequence 11 in the path. Hence if we are able to cover vertex t at the end of algorithm, then return TRUE because there is path from s to t without any edge with label 11 and return FALSE otherwise.

Below is the algorithm.

FIND_PATH(G=(V,E),s,t)

1. For every vertex v in V, set Color[v] = "White".

2. Q.Enqueue(s); //Add vertex s into empty queue Q

3. While Q.NotEmpty() :-

4..........u = Q.Dequeue() //Dequeue the front element from the queue Q

5..........For all vertex v adjacent to u :-

6..................if (Color[v] != White) then continue //since vertex v has already been explored, so skip it

7..................else if (Label[v]==1 AND Label[u] ==1) then continue //since we cannot include edge (u,v) if both has Label 1

8..................else

9..........................Parent[v] = u //Edge (u,v) will be part of BFS tree with u being predecessor of v

10........................Color[v] = "Gray" //Since vertex v has been included in BFS tree

11........................Q.Enqueue(v) //Add vertex v into the queue Q

12........Color[u] = "Black" //Since this has been completely explored

13. If Color[t] == "White" //this means that t has not been included in BFS tree

14...........Return False //Since no path exist from s to t without edge label 11

15. Else

16...........Return Tree //since vertex t has been included in BFS tree

Proof of correctness : - Since our algorithm include a vertex v if and only if there is some path from s to v without any edge with label 11 in it. Hence if there exist some path from s to t without any edge with label 11 in it, then clearly all the nodes in the path from s to t will be in BFS tree and at the end vertex t will also be included. Hence our algorithm is correct.

Time complexity = Time complexity of BFS = O(V+E).

Please comment for any clarification.