Non Bored Jogger Problem

Turns out I solve an NP-Complete problem almost every day. We were given a practice proof in class yesterday (final class of the semester) to show the Non-Bored Jogger Problem (NBJP) was NP-Complete. This is the problem of finding a path through a graph starting and finishing at a given vertex such that the total weight of the edges is equal to a given sum. The proof is pretty straightforward as a reduction from SUBSET-SUM (finding a subset of numbers in a set that sum to a given total).

NBJP is NP by demonstration: Given a path, simply check that all the consecutive edges in the path are in the graph and sum the edge weights. This is a 1-pass algorithm with a polynomial lookup performed each pass, so it's clearly P.

To transform SUBSET-SUM(S, T) to NBJP(G(E,V), T), let V have a vertex for each member of S, plus a start/finish vertex, v0. E contains an edge from v0 to every other edge with a weight equal to the corresponding value of the member of S, plus a zero-weight return edge. This is also a 1-pass algorithm through S with polynomial time inserts into G(E,V).

If SUBSET-SUM(S,T) with a solution S' then the path from v0 to and from each vertex corresponding to the elements of S' will have total weight of T. There are no repeated edges since each element occurs only once in S'. So, NBJP(G(E,V),T) has a solution.

If NBJP(G(E,V),T) has a solution V' then S' = {s| corresponding v is in V  - {v0}} has sum equal to T. V' does not repeat any nodes other than v0 since there is only one way to get from v0 to each v. Thus SUBSET-SUM(S,T) is solved by S'.