This problem treats the city of Reduct, a city created from scratch by forward-t

Question

This problem treats the city of Reduct, a city created from scratch by forward-thinking people. City designers are working on the layout of Reduct. Instead of laying out the streets in a grid system, they have decided to designate certain landmarks (e.g. City hall, grocery store, gas station, library) and make roads connecting the landmarks. They initially want to spend as little money as possible on road building, so they have asked you to design a network of roads that connect all landmarks together with as little road as possible. Show that you can solve this problem in polynomial time by reducing it to a known polynomial time algorithm. Two generations later, Reduct has grown into a bustling city. The minimal road network you designed has grown into a sophisticated network with many roads providing excellent transportation for city-dwellers. City leaders have decided to hold a 50th anniversary parade. They would like the parade to follow a route that visits each of the original landmarks and ends up where it started. Since the parade entries will cover the entire road, each road segment can only be on the parade route once. Parade designers have asked your granddaughter (who is also an excellent engineer like you) to design just such a route. Show that this will be a difficult task to solve exactly (i.e. there is no known polynomial time solution) by reducing a known NP-Complete problem to the parade route-finding problem.

Explanation / Answer

9 a) Let us model the landmarks as nodes and the paths between the landmarks as edges connecting those nodes on a graph. for each road (edge onthe graph) let the weight be the cost of constructing the road. To minimize the cost of constructing the roads, we need to find the set of edges on the graph such that the sum of their weight is minimum. This can be done by finding the minimum spanning tree (MST) of the modelled graph. To find the MST, we have dijkstra's algorithm which runs in polynomial time of O(|E|+|V|log|V|) where E is the set of edges and V is the set of vertices. Thus the problem is reduced to finding MST problem and can be solved in polynomial time.

9 b) Let us again model the landmarks and the roads as nodes and edges on a graph. Now, let the weight of each edge be the distance between the nodes. The parade would then be visiting each node on the graph exactly once and return to the origin such that no edge is traversed more than once. This problem can be reduced to the traveling salesman problem (TSP) with time complexity O(2n). Since TSP is a NP-complete problem and the above problem can be reduced to it, it is also NP-complete.

Related Questions

Navigate

• Browse (All)
• Browse T
• Subjects

---

---

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