Question

The physical layout of a VLSI circuit is tightly linked to overall circuit performance; moreover, determining the wiring layout of a circuit is one of the most difficult steps in the VLSI chip design process. In particular, you are given a set of components that must be connected by wires, preferably as cheaply as possible. Obviously you will use a tree to connect up your components, but unlike the minimum spanning tree problem, you are permitted to construct or select intermediary connection points to reduce the cost of the tree. The result is called the minimum Sinner tree. More precisely, you have an undirected graph G = (V, E) with edge costs c_e greaterthanorequalto 0 for each edge e elementof E, and a set of notes S V (called the terminals the three large nodes in the example). A Steiner tree for S is a tree T in G that must span all the nodes in S, however, you may also use other nodes in V if it allows you to obtain a cheaper T overall. As demonstrated in the example, including additional nodes may yield a cheaper tree. Any vertex in T\S is called a Steiner node. The problem of determining whether there is a Steiner tree of cost lessthanorequalto k for some extra input k is known as the Steiner minimum tree problem (SMT). a. Show that SMT is NP-hard (think: SET COVER or VERTEX COVER). b. Give an efficient algorithm to find the minimum-cost Steiner tree in the case that |S| = 2. c. Give an efficient algorithm to find the minimum-cost Steiner tree in the case that |S| = |V|. d. Give a 2-approximation for the minimum-cost Steiner tree problem (for any set S).

Answer 1