Show that Subset Sum reduces to Walking Tourist in Polynomial time. Consider the

Question

Show that Subset Sum reduces to Walking Tourist in Polynomial time.

Consider the following two decision problems. Problem: Subset Sum Input Instance: Set of of non-negative numbers S and an integer k lessthan 0. Decision: Is there a subset S' of S such that sum of numbers in Sprime equals k. Problem: Walking Tourist Input Instance: A weighted graph G (with non-zero, non-negative weights on edges), a special vertex s and an integer L. Decision: Is there a tour that starts at s and ends at s such that the total length of the tour equals L and no vertex (other than s) is visited multiple times? The tour may visit vertex s multiple times. Show that Subset Sum reduces to Walking Tourist in Polynomial time.

Explanation / Answer

Let (L, G) be an instance of the subset sum in which L is a list of numbers & G is the target sum. Let S=L. Let

L be the list which is formed by the addition of S+G,2SG to L.

1) If we have a sub-list ML which sums up to G, then L can be partitioned into 2 equal parts:

M{2SG} and LM{S+G}. In fact, the 1st part sums to G+(2SG)=2S, and the 2nd to (SG)+(S+G)=2S.

2) If L is able to be partitioned into 2 equal parts P1,P2 then there will be a sub-list of L summing to G. In fact since (S+G)+(2SG)=3S and each part sums to 2S, the 2 elements belong to the separate parts. Without the loss of generality 2SBP1. The remaining elements in P1 belong to L and add up to B.

Related Questions

Navigate

• Browse (All)
• Browse S
• Subjects

---

---

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