1. A group of network designers at the communication company SNet have a connect

Question

1. A group of network designers at the communication company SNet have a
connected graph G(E,V) in which nodes represent sites that want to communicate. Each edge e is
a communication link with a given distinct bandwidthBe . For each pair of nodes u,v?V they
want to select a single path P on which to communicate. The bandwidth of this path B(P) is the
minimum bandwidth of any edge on the path P. The best achievable bandwidth (BAB) for the
pair u, v is the maximum bandwidth over all paths between u and v in G.

The problem is to find BAB for every pair of nodes in the graph, which is very complicated due
to the huge number of paths. A network designer who has taken algorithms makes a bold suggestion:
Maybe one can find a spanning tree T of G so that for every pair of nodes u and v in the graph,
the unique path between u and v in the tree actually attains the BAB. The idea is tossed away by
his colleagues since there is a natural reason for skepticism: each pair of nodes might want a very
different path to get BAB; why should there be a single tree that simultaneously makes everybody
happy? But after some failed attempts to rule out the idea, designers at SNet began to
suspect it could be possible. Prove that such a spanning tree exists and give an efficient algorithm
to find it.

2. T (true), F(false), I (inconclusive) in front of each of the following statements.
Justify your answers.
( ) NP-complete problems are a subset of P problems.
( ) Suppose that P1 is an NP-complete problem, and that P2 can be converted into P1 by a
polynomial bounded algorithm. Then P2 is also an NP-complete problem.
( ) Suppose that every vertex of a graph has degree 2. Then the graph is colorable with at most 3
colors.
( ) The best fit off-line bin packing algorithm requires more number of bins than the best fit on-line bin packing for the same set of items.

Explanation / Answer

Question-1.
    Intuition:
    First choose the edge with maximum weight, say (u,v). Now, consider all the paths between these two
    nodes. Among all these paths, the edge (u,v) has the maximum bandwidth. Hence, we must choose
    this edge in the spanning tree.
    Next, consider the edge with second largest weight, say (a,b). Again, among all the paths between (a,b),
    the direct edge path will have the maximum bandwidth. So, we have to choose this edge.

    Now, consider the third largest weight edge say (p,q).
    We can have two cases:
    Case-1: Including this edge doesn't form a cycle: The, simply add this edge to the tree formed.
    Case-2:   Inlcuding this edge forms a cylce. In that case, we discard this edge.
           We already have a path from p to q. Note that all edges in this path have weight >= weight(p,q)
           So, the maximum bandwidth p,q will be the minimum weight edge in this path >= weight(p,q).

     Similarly for other nodes, create spanning tree in this fashion which satisfy every pair of nodes,
     and this spanning tree is none other than Maximum Spanning Tree. And all we need to find the
     maximum spanning tree in the given graph which can be found using below algorithm:

Algorithm for finding maximum spanning tree:

Question 2.

   (i)   I (inconclusive), since it is undecidable to prove P=NP equality.
   (ii) False, since it is also necessary to prove that problem P2 is in NP.
   (iii) True.
   (iv) False (but not fully sure)

Related Questions

Navigate

• Browse (All)
• Browse 1
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.