<p>Since you specifically ask later about the version of the problem in which the given path is restricted in how many times it visits each vertex/edge, I assume that the original version of the problem has no such restriction. In other words, in the original version of the problem the "path" is actually a trail (i.e., any sequence of vertices such that each contiguous pair has an edge between them). Thus I will refer to the original version of the problem as the trail max-weight travel problem. The other version, in which the number of uses of each edge/vertex is limited, includes the case in which each edge/vertex can be used at most once (i.e., the trail used must be a simple path); I will call that subproblem the simple path max-weight travel problem.</p>

<p>Below, I prove that trail max-weight travel is weakly NP-hard and that simple path max-weight travel is strongly NP-hard.</p>

<h1>trail max-weight travel is weakly NP-hard</h1>

<p>We reduce from the Unbounded Knapsack problem: we are given a list of pairs of positive integers $(c_1, s_1), \ldots, (c_k, s_k)$ where pair $i$ represents a type of item with cost $c_i$ and size $s_i$, a maximum size $S$, and a minimum cost $C$, and we are asked to decide whether it is possible to choose some quantity of each item so that the total size is at most $S$ and the total cost is at least $C$.</p>

<p>Suppose we are given an input $(c_1, s_1), \ldots, (c_k, s_k), S, C$ to the knapsack problem. Let $H &gt; S$ be any big ("huge") number. Then we build an instance of trail max-weight travel as follows:</p>

<ul>
<li>Set the graph size $n$ to be $k + 1$. Let $1, \ldots, k+1$ be the vertices of graph $K_n$.</li>
<li>Set the deadline $D$ to be $(k+1)H + S$.</li>
<li>If $1 \le i &lt; j \le k+1$ then set the weight $w(e_{ij})$ to be $0$. Set the travel time $l(e_{ij})$ to be $(j-i)H$.</li>
<li>If $1 \le i \le k$ then set the weight $w(e_{ii})$ to be $c_i$. Set the travel time $l(e_{ii})$ to be $s_i$.</li>
<li>If $i = k+1$ then set the travel time $l(e_{ii})$ to be $H$. Set weight $w(e_{ii})$ to be some number $M$ that is greater than $D (\max_{i = 1}^k \frac{c_i}{s_i})$. </li>
<li>Set the start node to be vertex $1$.</li>
</ul>

<p>We will show that a trail of total travel time $D$ has a weight of at least $M + C$ if and only if the answer to the given knapsack instance is "yes". This is sufficient to show NP-hardness.</p>

<p>There are two possible types of trails: those that use edge $e_{ii}$ with $i = k+1$ and those that don't. Call this edge $e'$. </p>

<p>The maximum weight gained per unit of travel time over all edges other than $e'$ is $\max_{i = 1}^k \frac{c_i}{s_i}$. Thus, any trail that does not use edge $e'$ will have a total weight of at most $D (\max_{i = 1}^k \frac{c_i}{s_i}) &lt; M$. Thus, trails that do not use edge $e'$ will have total weight less than $M$. </p>

<p>Clearly, some trail (whose travel time is at most the deadline) has total weight at least $M + C$ if and only if a trail using edge $e'$ (with travel time at most the deadline) has total weight at least $M + C$. Using edge $e'$ requires reaching vertex $k+1$ from vertex $1$. This requires using a travel time of at least $kH$. Then using edge $e'$ requires an additional travel time $H$. After that, there is not enough time left in the deadline to use edge $e'$ again. Thus, any trail whose travel time is at most the deadline and whose weight is at least $M + C$ will use edge $e'$ exactly once. </p>

<p>Since traveling between vertices adds no weight, it should be clear that the optimal solution will always spend the minimum possible travel time between vertices. Fortunately, this is possible without bypassing any vertex (by going through the vertices in order $1, 2, \ldots, k+1$). This means that there is always an optimal solution to the produced trail max-weight travel instance in which we pass through the vertices in order $1, 2, \ldots, k+1$ taking one self loop at vertex $k+1$ (in particular edge $e'$) and some number of self loops at the other vertices. Traveling between the vertices has travel time $kH$ and weight $0$. The self loop at vertex $k+1$ has travel time $H$ and weight $M$. Thus, in order for this optimal solution to reach a weight of at least $M + C$ within a deadline of $D = (k+1)H+S$, it must be the case that the total travel time used on the self loops at vertices $\{1, \ldots, k\}$ is at most $S$ and the total weight gained at those self loops is at least $C$. Since self loop $e_{ii}$ has travel time $s_i$ and weight $c_i$, this is exactly equivalent to the knapsack instance we started with.</p>

<h1>simple path max-weight travel is strongly NP-hard</h1>

<p>We reduce from the following NP-hard version of the Hamiltonian path problem: given graph $G$ and vertex $v$, decide whether there exists a Hamiltonian path in $G$ starting at $v$.</p>

<p>Suppose we are given an instance of this problem with graph $G = (V, E)$ and vertex $v \in  V$. Then we build an instance of simple path max-weight travel as follows:</p>

<ul>
<li>Set the graph size $n$ to be $|V|$.</li>
<li>Set the deadline $D$ to be $|V| - 1$.</li>
<li>Identify each vertex of $K_n$ with each vertex of $G$. Then for each edge $e$ of $K_n$: (1) if $e$ corresponds to an edge of $G$, set the travel time $l(e)$ to be $1$ and (2) if $e$ does not correspond to an edge of $G$, set the set the travel time $l(e)$ to be $|V|$. In all cases, set the weight of each edge to be $1$.</li>
<li>Set the start node to be the node corresponding to $v$.</li>
<li>As always in the simple path max-weight travel problem, each vertex/edge can be used at most once: $h(\cdot) = 1$.</li>
</ul>

<p>Each edge has the same weight, so maximizing weight is equivalent to choosing the longest simple path whose total travel time does not exceed the deadline. The only edges that can be used without exceeding the deadline exactly correspond to edges in $G$. Furthermore, each such edge has the same time limit: $1$. Thus, solving this instance is equivalent to finding the longest simple path in $G$ starting at $v$ of length at most $|V| - 1$. Such a path of length exactly $|V| - 1$ is a Hamiltonian path, so solving this problem requires being able to solve the Hamiltonian path problem in $G$. Thus the reduction is correct. Note that the size of each number in this proof is at most polynomial in the size of the input instance, so this is a proof of strong NP-hardness.</p>

CC BY-SA 3.0
2017-07-25T04:40:51.557Z
Thanks Mikhail, this is great answer. The only point is that, for the first part, $H$ cannot be any big number. It has to be bounded by a polynomial in the size of the input problem to keep the reduction polynomial. But I think we can figure it out pretty easily.
Helium
CC BY-SA 3.0
2017-07-25T09:58:30.490Z
About the first proof: How do you ensure that a self loop is not used more than once? Since there is no limit on the number of loops, one can go to vertex $i$ that has the $max \frac{c_i}{s_i}$ and loop there as long as the total time is $\le S$. It is similar to a version of the knapsack problem that it is possible to reuse an item as many times as you like.
Helium
CC BY-SA 3.0
2017-07-25T20:17:01.883Z
The fist proof should have been from Unbounded Knapsack, but anyways, you are right, it's a weakly NPC problem. See Marzio De Biasi's comment below OP.
Helium
CC BY-SA 3.0
2017-07-26T02:53:52.220Z
@Helium That sounds right. I guess I used the wrong problem name, but notice that when I defined the "Knapsack problem" I actually used the definition for which the reduction works (the definition that actually defines the Unbounded Knapsack problem). I am about to edit to fix that naming issue.
Mikhail Rudoy
CC BY-SA 3.0
2017-07-24T05:56:07.640Z
2017-07-26T02:55:16.600Z
2017-07-26T02:55:16.600Z
Mikhail Rudoy
<p>Given a deadline $D&gt;0$ and a complete graph $K_n$ (with loops) in which each edge $e_{ij}$ has a weight $w(e_{ij}) \ge 0$ and a travel time $l(e_{ij}) &gt; 0$. Starting from one of the nodes, we want to find a path $P$ so that $\sum_{e \in P}l(e) \le D$ and $\sum_{e \in P} w(e)$ is maximized.</p>

<p>Questions:</p>

<ol>
<li><p>This problem can be solved using a pseudo polynomial algorithm by iterating over time $t=1,\cdots,D$.
Let $S_{v,t}$ be the weight of the optimal path until time $t$ ending at vertex $v$.
$$
S_{v,t}=\max(\max_u S_{u,t-l(e_{uv})},S_{v,t-1})
$$
Therefore, it seems a (weakly) NP-hard problem to me, but I have no proof for it yet. Do you have any idea?</p></li>
<li><p>In a more complicated version of the problem, the path can visit each vertex $v$ and each edge $e$ at most $h(v)$ and $h(e)$ times. The above algorithm does not work for this constraint version of the problem. Any better solution?</p></li>
</ol>

<p>The problem can be modeled using ILP:
$$
\begin{align}
{\tt Maximize} \quad &amp; \sum_i \sum_j w(e_{ij}) X_{ij} \\
&amp;\sum_i \sum_j l(e_{ij}) X_{ij} \le D \\
&amp; \sum_i X_{i0} = \sum_j X_{0j} = 1\\
&amp; \sum_i X_{iv} = \sum_j X_{vj}, \quad {\tt for \; all \;} v = 1,\cdots,n
\end{align}
$$</p>

<p>Where $X_{ij}$ denotes the number of times the path goes through edge $e_{ij}$.
The first constraint enforces the deadline and the last two are the conservation law (number of times entering a node is the same as the number of times exiting it). $v_0$ is a virtual node that traveling to/from it has zero weight and zero time.</p>

<p>In the more complicated version of the problem,
we have the following additional constraints:
$$
X_{ij} \le h(e_{ij})
$$
$$
\sum_i X_{iv} \le h(v) \quad {\tt for \; all \; }v
$$</p>

CC BY-SA 3.0
2017-07-23T18:36:23.410Z
Search for "orienteering" and you will find references.
Chandra Chekuri
CC BY-SA 3.0
2017-07-24T10:13:31.057Z
Even without delay time, the problem is np-complete in the strong sense, since there is a reduction from/to the Hamiltonian path problem in general graphs: Take a graph $G$ on $n$ vertices and set the weight of edge in $k_n$ to 1 if there is a corresponding edge in $G$ otherwise set its weight to zero ($\epsilon$). There is a path of length $n$ in the clique if and only if there is a Hamiltonian path in the original graph (we can choose $n$ different start vertices). So w.h.p. your algorithm is either wrong or not in P.
Saeed
CC BY-SA 3.0
2017-07-25T03:55:58.990Z
@Saeed That's not true if the "path" is allowed to be any sequence of vertices with edges between them. That is the case solved by the given algorithm. Also, in that case, the reduction you gave always outputs a graph where you can just go back and forth across one edge $n$ times in order to accumulate the best possible weight.
Mikhail Rudoy
CC BY-SA 3.0
2017-07-25T07:33:32.433Z
@Mikhail, what you say is usually called walk not path. Usually if one uses the term path and means walk, they should clearly state it.
Saeed
CC BY-SA 3.0
2017-07-25T07:41:52.520Z
@Saeed I think Mikhail is right. Nothing prevents repeated vertices in your proof. You can use the second (constrained) version of the problem and put a limit on the number of visits to each vertex (similar to second part of Mikhail's answer below), but I don't see a way to do so for the first (unconstrained) version.
Helium
CC BY-SA 3.0
2017-07-25T09:54:35.550Z
By default, definition of path says all vertices are distinct (for instance see wiki or any graph theoretic book you have in mind), hence there is no need to explicitly state it in the proof or prevent repeated vertices. I also didn't look at the second part of your question when I was writing the comment, but yes it works there (even if by path you mean a walk).
Saeed
CC BY-SA 3.0
2017-07-25T10:01:10.970Z
A **simple** path does not contain repeated vertices https://www.wikiwand.com/en/Path_(graph_theory)
But in general, it may contain.
Helium
CC BY-SA 3.0
2017-07-25T12:42:23.283Z
@Helium: In the first case (walk) your problem is equivalent to the *Unbounded Knapsack Problem* which remains NP-hard as proven by Lueker, G.S. (1975). "Report No. 178, Computer Science Laboratory, Princeton". You can find some insights about approximation algorithms in this pdf: http://www.or.deis.unibo.it/kp/Chapter3.pdf (from the book "Knapsack Problems, Algorithms and Computer Implementations" by S.Martello and P.Toth)
Marzio De Biasi
CC BY-SA 3.0
2017-07-25T20:14:33.577Z
@MarzioDeBiasi I think your comment is the key to a few issues. The first part of Mikhail's answer is correct, but the reduction should have been from Unbounded Knapsack.
Helium
CC BY-SA 3.0
2017-07-25T22:31:16.433Z
@Helium: I think that the reduction from Unbounded Knapsack (UK) is immediate: the edges of the (complete) graph correspond to the items of UK, the edge weights correspond to the profit of the items,the edge lengths correspond to the weight of the items. *The only caveat is to double the edges/items* because in a path the same edge cannot be traversed consecutively so you need $e_i, e'_i$ with $w(e_i)=w(e'_i)$,$l(e_i)=l(e'_i)$ in order to "simulate" the picking of the same item many times (a loop of 2 edges with the same weight/length). Note:UK doesn't change if you double the number of items.
Marzio De Biasi
CC BY-SA 3.0
2017-07-26T11:06:57.560Z
@Helium, more often we do not distinguish simple paths from paths except for exceptional usages, for instance if we have a situation in which 3 different structures appear: 1. no vertex repeats, 2. we may repeat vertices but not edges, 3. both edges and vertices can be repeated. In such cases we may use 3 different terms simple path, path, walk. Other than that I don't know any place distinguishing path and the (somehow fake) term simple path. Read first line of wiki more carefully. I can show numerous papers that they simply use path not simple path.
Saeed
<graph-algorithms><np-hardness><linear-programming><integer-programming><dynamic-programming>
Max weight travel on a graph with deadline
Helium
# Max weight travel on a graph with deadline

(Asked by: username_0 on 2017-07-23)

Given a deadline $D>0$ and a complete graph $K\_n$ (with loops) in which each edge $e\_{ij}$ has a weight $w(e\_{ij}) \ge 0$ and a travel time $l(e\_{ij}) > 0$. Starting from one of the nodes, we want to find a path $P$ so that $\sum\_{e \in P}l(e) \le D$ and $\sum\_{e \in P} w(e)$ is maximized.

Questions:

1. This problem can be solved using a pseudo polynomial algorithm by iterating over time $t=1,\cdots,D$.
   Let $S\_{v,t}$ be the weight of the optimal path until time $t$ ending at vertex $v$.
   $$
   S\_{v,t}=\max(\max\_u S\_{u,t-l(e\_{uv})},S\_{v,t-1})
   $$
   Therefore, it seems a (weakly) NP-hard problem to me, but I have no proof for it yet. Do you have any idea?
2. In a more complicated version of the problem, the path can visit each vertex $v$ and each edge $e$ at most $h(v)$ and $h(e)$ times. The above algorithm does not work for this constraint version of the problem. Any better solution?

The problem can be modeled using ILP:
$$
\begin{align}
{\tt Maximize} \quad & \sum\_i \sum\_j w(e\_{ij}) X\_{ij} \\
&\sum\_i \sum\_j l(e\_{ij}) X\_{ij} \le D \\
& \sum\_i X\_{i0} = \sum\_j X\_{0j} = 1\\
& \sum\_i X\_{iv} = \sum\_j X\_{vj}, \quad {\tt for \; all \;} v = 1,\cdots,n
\end{align}
$$

Where $X\_{ij}$ denotes the number of times the path goes through edge $e\_{ij}$.
The first constraint enforces the deadline and the last two are the conservation law (number of times entering a node is the same as the number of times exiting it). $v\_0$ is a virtual node that traveling to/from it has zero weight and zero time.

In the more complicated version of the problem,
we have the following additional constraints:
$$
X\_{ij} \le h(e\_{ij})
$$
$$
\sum\_i X\_{iv} \le h(v) \quad {\tt for \; all \; }v
$$

**Tags:** graph-algorithms, np-hardness, linear-programming, integer-programming, dynamic-programming
> **Comments:**
> **username_1**: Search for "orienteering" and you will find references.  
> **username_2**: Even without delay time, the problem is np-complete in the strong sense, since there is a reduction from/to the Hamiltonian path problem in general graphs: Take a graph $G$ on $n$ vertices and set the weight of edge in $k_n$ to 1 if there is a corresponding edge in $G$ otherwise set its weight to zero ($\epsilon$). There is a path of length $n$ in the clique if and only if there is a Hamiltonian path in the original graph (we can choose $n$ different start vertices). So w.h.p. your algorithm is either wrong or not in P.  
> **username_3**: @Saeed That's not true if the "path" is allowed to be any sequence of vertices with edges between them. That is the case solved by the given algorithm. Also, in that case, the reduction you gave always outputs a graph where you can just go back and forth across one edge $n$ times in order to accumulate the best possible weight.  
> **username_2**: @Mikhail, what you say is usually called walk not path. Usually if one uses the term path and means walk, they should clearly state it.  
> **username_0**: @Saeed I think Mikhail is right. Nothing prevents repeated vertices in your proof. You can use the second (constrained) version of the problem and put a limit on the number of visits to each vertex (similar to second part of Mikhail's answer below), but I don't see a way to do so for the first (unconstrained) version.  
> **username_2**: By default, definition of path says all vertices are distinct (for instance see wiki or any graph theoretic book you have in mind), hence there is no need to explicitly state it in the proof or prevent repeated vertices. I also didn't look at the second part of your question when I was writing the comment, but yes it works there (even if by path you mean a walk).  
> **username_0**: A **simple** path does not contain repeated vertices https://www.wikiwand.com/en/Path_(graph_theory) But in general, it may contain.  
> **username_4**: @Helium: In the first case (walk) your problem is equivalent to the *Unbounded Knapsack Problem* which remains NP-hard as proven by Lueker, G.S. (1975). "Report No. 178, Computer Science Laboratory, Princeton". You can find some insights about approximation algorithms in this pdf: http://www.or.deis.unibo.it/kp/Chapter3.pdf (from the book "Knapsack Problems, Algorithms and Computer Implementations" by S.Martello and P.Toth)  
> **username_0**: @MarzioDeBiasi I think your comment is the key to a few issues. The first part of Mikhail's answer is correct, but the reduction should have been from Unbounded Knapsack.  
> **username_4**: @Helium: I think that the reduction from Unbounded Knapsack (UK) is immediate: the edges of the (complete) graph correspond to the items of UK, the edge weights correspond to the profit of the items,the edge lengths correspond to the weight of the items. *The only caveat is to double the edges/items* because in a path the same edge cannot be traversed consecutively so you need $e_i, e'_i$ with $w(e_i)=w(e'_i)$,$l(e_i)=l(e'_i)$ in order to "simulate" the picking of the same item many times (a loop of 2 edges with the same weight/length). Note:UK doesn't change if you double the number of items.  
> **username_2**: @Helium, more often we do not distinguish simple paths from paths except for exceptional usages, for instance if we have a situation in which 3 different structures appear: 1. no vertex repeats, 2. we may repeat vertices but not edges, 3. both edges and vertices can be repeated. In such cases we may use 3 different terms simple path, path, walk. Other than that I don't know any place distinguishing path and the (somehow fake) term simple path. Read first line of wiki more carefully. I can show numerous papers that they simply use path not simple path.  

---

## 1 answers

### Answer by username_3 on 2017-07-24. Score: 1

Since you specifically ask later about the version of the problem in which the given path is restricted in how many times it visits each vertex/edge, I assume that the original version of the problem has no such restriction. In other words, in the original version of the problem the "path" is actually a trail (i.e., any sequence of vertices such that each contiguous pair has an edge between them). Thus I will refer to the original version of the problem as the trail max-weight travel problem. The other version, in which the number of uses of each edge/vertex is limited, includes the case in which each edge/vertex can be used at most once (i.e., the trail used must be a simple path); I will call that subproblem the simple path max-weight travel problem.

Below, I prove that trail max-weight travel is weakly NP-hard and that simple path max-weight travel is strongly NP-hard.

# trail max-weight travel is weakly NP-hard

We reduce from the Unbounded Knapsack problem: we are given a list of pairs of positive integers $(c\_1, s\_1), \ldots, (c\_k, s\_k)$ where pair $i$ represents a type of item with cost $c\_i$ and size $s\_i$, a maximum size $S$, and a minimum cost $C$, and we are asked to decide whether it is possible to choose some quantity of each item so that the total size is at most $S$ and the total cost is at least $C$.

Suppose we are given an input $(c\_1, s\_1), \ldots, (c\_k, s\_k), S, C$ to the knapsack problem. Let $H > S$ be any big ("huge") number. Then we build an instance of trail max-weight travel as follows:

* Set the graph size $n$ to be $k + 1$. Let $1, \ldots, k+1$ be the vertices of graph $K\_n$.
* Set the deadline $D$ to be $(k+1)H + S$.
* If $1 \le i < j \le k+1$ then set the weight $w(e\_{ij})$ to be $0$. Set the travel time $l(e\_{ij})$ to be $(j-i)H$.
* If $1 \le i \le k$ then set the weight $w(e\_{ii})$ to be $c\_i$. Set the travel time $l(e\_{ii})$ to be $s\_i$.
* If $i = k+1$ then set the travel time $l(e\_{ii})$ to be $H$. Set weight $w(e\_{ii})$ to be some number $M$ that is greater than $D (\max\_{i = 1}^k \frac{c\_i}{s\_i})$.
* Set the start node to be vertex $1$.

We will show that a trail of total travel time $D$ has a weight of at least $M + C$ if and only if the answer to the given knapsack instance is "yes". This is sufficient to show NP-hardness.

There are two possible types of trails: those that use edge $e\_{ii}$ with $i = k+1$ and those that don't. Call this edge $e'$.

The maximum weight gained per unit of travel time over all edges other than $e'$ is $\max\_{i = 1}^k \frac{c\_i}{s\_i}$. Thus, any trail that does not use edge $e'$ will have a total weight of at most $D (\max\_{i = 1}^k \frac{c\_i}{s\_i}) < M$. Thus, trails that do not use edge $e'$ will have total weight less than $M$.

Clearly, some trail (whose travel time is at most the deadline) has total weight at least $M + C$ if and only if a trail using edge $e'$ (with travel time at most the deadline) has total weight at least $M + C$. Using edge $e'$ requires reaching vertex $k+1$ from vertex $1$. This requires using a travel time of at least $kH$. Then using edge $e'$ requires an additional travel time $H$. After that, there is not enough time left in the deadline to use edge $e'$ again. Thus, any trail whose travel time is at most the deadline and whose weight is at least $M + C$ will use edge $e'$ exactly once.

Since traveling between vertices adds no weight, it should be clear that the optimal solution will always spend the minimum possible travel time between vertices. Fortunately, this is possible without bypassing any vertex (by going through the vertices in order $1, 2, \ldots, k+1$). This means that there is always an optimal solution to the produced trail max-weight travel instance in which we pass through the vertices in order $1, 2, \ldots, k+1$ taking one self loop at vertex $k+1$ (in particular edge $e'$) and some number of self loops at the other vertices. Traveling between the vertices has travel time $kH$ and weight $0$. The self loop at vertex $k+1$ has travel time $H$ and weight $M$. Thus, in order for this optimal solution to reach a weight of at least $M + C$ within a deadline of $D = (k+1)H+S$, it must be the case that the total travel time used on the self loops at vertices $\{1, \ldots, k\}$ is at most $S$ and the total weight gained at those self loops is at least $C$. Since self loop $e\_{ii}$ has travel time $s\_i$ and weight $c\_i$, this is exactly equivalent to the knapsack instance we started with.

# simple path max-weight travel is strongly NP-hard

We reduce from the following NP-hard version of the Hamiltonian path problem: given graph $G$ and vertex $v$, decide whether there exists a Hamiltonian path in $G$ starting at $v$.

Suppose we are given an instance of this problem with graph $G = (V, E)$ and vertex $v \in V$. Then we build an instance of simple path max-weight travel as follows:

* Set the graph size $n$ to be $|V|$.
* Set the deadline $D$ to be $|V| - 1$.
* Identify each vertex of $K\_n$ with each vertex of $G$. Then for each edge $e$ of $K\_n$: (1) if $e$ corresponds to an edge of $G$, set the travel time $l(e)$ to be $1$ and (2) if $e$ does not correspond to an edge of $G$, set the set the travel time $l(e)$ to be $|V|$. In all cases, set the weight of each edge to be $1$.
* Set the start node to be the node corresponding to $v$.
* As always in the simple path max-weight travel problem, each vertex/edge can be used at most once: $h(\cdot) = 1$.

Each edge has the same weight, so maximizing weight is equivalent to choosing the longest simple path whose total travel time does not exceed the deadline. The only edges that can be used without exceeding the deadline exactly correspond to edges in $G$. Furthermore, each such edge has the same time limit: $1$. Thus, solving this instance is equivalent to finding the longest simple path in $G$ starting at $v$ of length at most $|V| - 1$. Such a path of length exactly $|V| - 1$ is a Hamiltonian path, so solving this problem requires being able to solve the Hamiltonian path problem in $G$. Thus the reduction is correct. Note that the size of each number in this proof is at most polynomial in the size of the input instance, so this is a proof of strong NP-hardness.

> **Comments:**
> **username_0**: Thanks Mikhail, this is great answer. The only point is that, for the first part, $H$ cannot be any big number. It has to be bounded by a polynomial in the size of the input problem to keep the reduction polynomial. But I think we can figure it out pretty easily.  
> **username_0**: About the first proof: How do you ensure that a self loop is not used more than once? Since there is no limit on the number of loops, one can go to vertex $i$ that has the $max \frac{c_i}{s_i}$ and loop there as long as the total time is $\le S$. It is similar to a version of the knapsack problem that it is possible to reuse an item as many times as you like.  
> **username_0**: The fist proof should have been from Unbounded Knapsack, but anyways, you are right, it's a weakly NPC problem. See Marzio De Biasi's comment below OP.  
> **username_3**: @Helium That sounds right. I guess I used the wrong problem name, but notice that when I defined the "Knapsack problem" I actually used the definition for which the reduction works (the definition that actually defines the Unbounded Knapsack problem). I am about to edit to fix that naming issue.  

---

