Consider the following two decision problems.

Problem: Subset Sum Input Instance: Set of of non-negative numbers S and an integer k > 0.

Decision: Is there a subset S 0 of S such that sum of numbers in S 0 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.