Due 4/13/99

Problem 1

For a  undirected graph G = (V,E), with vertex set V and edge set E, a simple circuit in G is a sequence <v₁,v₂,...v_k> of distinct vertices from V such that {v_i,v_i+1} is in E for 1 <= i < k and such that {v_k,v₁} is in  E. A Hamiltonian Circuit in G is a simple circuit that includes all the vertices of G. The decision version of the Hamiltonian Circuit problem is :  Given a graph G  = (V,E), determine if G contains a Hamiltonian Circuit.

Suppose you are given a (polynomial time) algorithm  DHC that solves this decision problem.  That is, DHC(G) returns true if G contains a Hamiltonian circuit, and false otherwise.  (No such algorithm is known to exist, but assume for purposes of this problem that we have one.) Give an efficient (polynomial time) algorithm HC that actually finds and reports a Hamiltonian Circuit in the input graph G, if one exists, and reports negative if no Hamiltonian Circuit exists :

        HC :
        Input :     G = (V,E)
        Output :  A Hamiltonian Circuit  <v_i1,v_i2,.....v_ik>  (see definition above), if one exists
                        and an empty list  otherwise.

A polynomial time algorithm in either of the above two cases means an algorithm that runs in time polynomial in n = |V| and m = |E|.   Your algorithm HC may have one or more calls to DHC, if needed.

Problem 2

We have seen how to find the Minimum Spanning Tree in a graph with weighted edges, using Kruskal's Greedy Algorithm and Prim's Algorithm. Sometimes, for the purpose of broadcasting in a network, we are interested in a different kind of Spanning Tree. We model the network as an undirected graph with vertices for the nodes of the network and edges representing links between the nodes (since the edges are undirected, the underlying network is assumed to have bidirectional links). There are no edge-weights, meaning that each link is equally good (or we do not care about link quality). We want to find a Spanning Tree for such a graph, such that the distance (in terms of number of edges or links) between any two vertices is not "too much" (we shall soon see what this means). Using such a Spanning Tree for broadcasting, there will be an upper bound on the number of hops a packet  has to travel.  Now let us formalize the notion.

Given an undirected connected graph G = (V,E), the distance between any two vertices i and j of G is defined as

        d(i,j) = number of edges on  the shortest path between i and j.

The diameter D(G) of the graph G is the maximum distance between any two of its vertices,  that is,

        D(G) = MAX _{i,j in V} d(i,j)

The diameter of a tree T is similarly defined (a tree is only a special kind of undirected connected graph). We are interested in spanning trees with low diameters. First, convince yourself that any spanning tree of graph G must have diameter at least D(G). Now, given a graph G, your task is to find a spanning tree T for G such that D(T) < 2D(G),  that is, the diameter of the spanning tree is at most twice the diameter of the underlying graph. Since D(T) is the maximum distance between any two nodes in T, we shall have an upper bound on the number of hops a packet has to travel if T is used as the broadcast tree.

In summary, give an efficient algorithm LowDiamSpanTree :

        LowDiamSpanTree :
        Input :     Undirected, connected, unweighted graph G = (V,E)
        Output:    Spanning Tree T such that D(T)  < 2D(G)

Give a high level outline of you algorithm first, with a careful explanation of why it works. Then give pseudo code for your algorithm, with comments. Finally, analyze the time and space complexity of your algorithm.

It would be great if some one can find a spanning tree whose diameter that is within a factor less than 2 of the diameter of the original graph.