CSE421-Homework 4 Solved

Prove or disprove the following claim: Suppose we are given a graph G where the cost of edge e is ce where all ce’s are positive. For simplicity, assume that all ce’s are distinct. Suppose T is the minimum spanning tree which is the output of the Kruskal’s algorithm. Now suppose we update the cost of every edge e to c2e. Then, T remains the minimum spanning tree of G. For example, in the following graph the tree shown in blue is the output of the Kruskal’s algorithm. In this case if we update the costs to 1,4,9 respectively the blue tree remains a minimum spanning tree.

 

2

P2) Given a connected undirected weighted graph G = (V,E) with positive weights on the edges, i.e., ce > 0 for all e. Design a polynomial time algorithm to find the minimum cost set of edges F ⊆ E such that if we delete all edges of F the remaining graph has no cycles. For simplicity assume that for any two edges e,f ∈ E, ce 6= cf. For example in the following example the optimum set F is F = {(a,b),(b,d)}.

 

P3) Suppose you are choosing between the following three algorithms:

a)    Algorithm A solves the problem by dividing it into seven subproblems of half the size, recursively solves each subproblem, and then combines the solution in linear time.

b)    Algorithm C solves the problem by dividing it into twenty seventh subproblems of one ninth the size, recursively solves each subproblem, and then combines the solutions in cubic time.

c)    Algorithm B solves problems of size n by recursively solving two subproblems of size n−4, and then combines the solution in constant time.

What are the running times of each of these algorithms? To receive full credit, it is enough to write down the running time.

P4) Given an array a1,...,an of n distinct integers, design an O(logn) time algorithm that finds ai such that ai > ai−1 and ai > ai+1. Note that you may output a1 if a1 > a2 and you may

4-1

output an if an > an−1. For example, given the sequence 3,4,6,5,1,2 you can output 6 or 2. If no such ai exists, output ”Impossible”.

P5) Extra Credit The spanning tree game is a 2-player game. Each player in turn selects an edge. Player 1 starts by deleting an edge, and then player 2 fixes an edge (which has not been deleted yet); an edge fixed cannot be deleted later on by the other player. Player 2 wins if he succeeds in constructing a spanning tree of the graph; otherwise, player 1 wins.

The question is which graphs admit a winning strategy for player 1 (no matter what the other player does), and which admit a winning strategy for player 2.

Show that player 1 has a winning strategy if and only if G does not have two edge-disjoint spanning trees. Otherwise, player 2 has a winning strategy