P rove that the following, Non-Bored Jogger’s Problem (NBJP) is NP complete. You
ID: 2247362 • Letter: P
Question
Prove that the following, Non-Bored Jogger’s Problem (NBJP) is NP complete. You are given as input: A weighted undirected graph G (loops and multiple edges are allowed and the weights of the edges are positive integers); A specified node v, which is called home; and An integer l>=0.You must determine if there exists a route for the Jogger (i.e a path in G) that starts at vertex v, never repeats an edge, and returns to v after traveling a distance of exactly l.
Hint: Reduce from SUBSET-SUM. Notice that you can create any graph you want, and the graph does not have to be simple. Answer clearly and completely the following questions.
1)Give a clear definition of the problem you choose in your proof
2)Give an example instance of the problem you choose in your proof
3)List all the steps of the proof
4)Provide a detailed proof
Explanation / Answer
NBJP is obviously in NP since we can check the solution by simply tracing the path given as a solution, adding up the edge weights, for cost at most O(|E|).
Next we reduce SUBSET-SUM to NBJP by the following steps:
We construct a graph with the single home node, v, with loop edges (self edges), one per integer in the Subset Sum input, with weights equal to the integers. (Note that this only works if we use Subset Sum as defined in the book, where the integers are all positive.) Finally, we set the jogger’s target distance equal to the target value k for the Subset Sum problem.
Now, as we know that edges can't be repeated in the solution to NBJP, any valid path for the jogger which matches the target value requires the jogger to transverse edges which can be seen as selecting integers from the SUBSET-SUM input which sum to k.
Construction of the NBJP is straightforwardly polynomial, since the number of edges is the same as the number of integers in the input. Recovery of the solution is similarly straightforward.
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.