Question

Describe a linear-time algorithm for computing a topological order of a DAG (b) A triangle in a graph G = (V, E) is a set of three distinct vertices u, v, w €V such that all three edges {u,v}, {u,w} and {v,w} exist in E. Show an algorithm that detects whether G has a triangle in time better than 0(³),where n = |V| is the number of vertices in the graph.[8 marks] (c) Define the ORTHOGONAL VECTORS problem (OV) and the Strong Exponential-Time Hypothesis (SETH), and state the connection between SETH and OV. (d) Illustrate the reduction from ORTHOGONAL VECTORS to graph diameter on the following input to OV: Set A contains vectors 1010, 1001, 0011, 0111, 1110 Set B contains vectors 1100, 1011, 0011, 1110, 1010 Draw the resulting graph and explain how the diameter of the resulting graph is connected to the status of the OV instance. Also state what implications this has for computing the diameter of a graph.

Fig: 1

Fig: 2

Fig: 3

Fig: 4

Fig: 5

Fig: 6

Fig: 7

Fig: 8