2023 Tutorial II CS60001 Advances in Algorithms Date 8 th November 2007 P1 Would the Djikstra s shortest path | Assignment Collections

Tutorial – II CS60001, Advances in Algorithms Date: 8 th November, 2007 (P1) Would the Djikstra’s shortest path algorithm work correctly for graphs with -ve edges. If not give an example where it would fail? (P2) Analyze the proof of correctness of Dijkstra’s shortest path algorithm to show that Dijkstra’s shortest path algorithm gives incorrect results for shortest paths in directed graphs with negative edge weights. (P3) The bottleneck capacity of an augmenting path in a flow network is the minimum residual capacity along that path. Design (and analyse) an efficient algorithm for finding an augmenting path with maximum bottleneck capacity among all possible augmenting paths. [Hints: You can modify Dijkstra’s algorithm.] (P4) Prove the following statement. Let M = (S, `) be any matroid. If x is an element of S such that x is not an extension of φ (where φ is the empty set), then x is not an extension of any independent subset A of S. (P5) For a network (G, s,t, c), the residual capacity r(u, v) for an edge (u, v) is defined as r(u, v) = c(u, v) − f(u, v) (where c is capacity and f is flow). Show that r(u, v) + r(v, u) = c(u, v) + c(v, u). (P6) Let G = {V, E}, be a bipartite graph with V1 ∪V2 = V and V1 ∩V2 = φ. Let G0 be the corresponding flow network where you have a source vertex s connected to all vertices in V1 and a sink vertex t connected from all vertices in V2 and the edges in G are directed from V1 to V2 in G0 . Find out a non-trivial upper bound on the length of any augmenting path found in G0 during the execution of the Ford-Fulkerson algorithm. (P7) Design and analyze an algorithm to determine if a text S is cyclic rotation of another string S 0 . The strings neo and one are cyclic rotations of each other. (P8) [Minimum Cost Flow Problem] A flow network with costs is a directed graph G = (V,E,c,k) where V is a set of vertices, E is a set of directed edges (arcs), each arc (u,v) ∈ E has a capacity c(u,v) ∈ R and similarly each arc (u,v) has a cost k(u,v) ∈ R. By convention, c(u,v)=k(u,v) = 0 for (u,v) ∈/ E. We allow positive as well as negative capacities and costs.A feasible flow f of value m is a real valued function f : V ∗V → R satisfying f(u, v) ≤ c(u, v)∀(u, v) ∈ E f(u, v) = −f(u, v)∀(u, v) ∈ E ∀u ∈ V-(s,t) X v∈V f(u, v) = 0 X v∈V f(s, v) = m and X v∈V f(t, v) = −m The cost of the flow f is given by cost(f) = X (u,v)∈V ∗V k(u, v)f(u, v) 1 The min cost flow problem is to find the feasible flow f in G that minimizes cost(f) among all feasible flows f in G. Can you derive a reduction of shortest path problem to this generalised min cost flow problem i.e. SHORTEST PATH ≤ MIN COST FLOW PROBLEM ? (P9) Show that P ⊆ NP. (P10) Let Π1 and Π2 be two problems such that Π1 ≤P Π2. Suppose that the problem Π2 can be solved in O(n k ) time and the reduction can be done in O(n j ) time. Show that the problem Π1 can be solved in O(n jk ) time. (P11) Prove that if an NP-Complete problem Π is shown to be solvable in polynomial time, then NP=P. (P12) Show that any cover of a clique of size n must have exactly n − 1 vertices. (P13) Give a direct reduction from the problem of VERTEX COVER to CLIQUE. (P14) Consider the following statement. If a problem Π ∈ NP and Π ≤P Π0 where Π0 is an NP-Complete problem, then Π is NP-Complete. State whether the above statement is true or false with a brief explanation. You may assume that P 6= NP. (P15) You are asked to design a polynomial time deterministic algorithm for finding a clique of size k (k is a fixed integer that you know before designing the algorithm. As an example, say you know before designing the algorithm that k = 5.). Can you design such a polynomial time deterministic algorithm? If you can, please give a sketch of such an algorithm. Now, does that contradict the fact that finding CLIQUE is NP-Complete? (P16) [Longest Path Problem] Given a weighted undirected graph G and two vertices s and t, find the longest weighted simple path from s to t. Recall that a simple path is a path that contains every vertex at most once. Show that the problem is NP-hard. (Hint: Use Hamiltonian Path Problem) (P17) A 3-colouring of a graph G = {V, E} is a map C : V → {R, G, B} that assigns one of the three colours to each vertex so that every edge (u, v) has two different colours from the set {R, G, B} for the two vertices u and v. The decision version of the problem asks if such a 3-colouring exists for the graph G. Show that 3-colouring is NP-Complete through a polynomial reduction. [Hints: You can try for a reduction from 3-SAT.] 2