Question

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′ of S such that sum of numbers in S′ 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.

Answer 1