# Max weight travel on a graph with deadline

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$$

• Search for "orienteering" and you will find references. – Chandra Chekuri Jul 23 '17 at 18:36
• 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 Jul 24 '17 at 10:13
• @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 Jul 25 '17 at 3:55
• 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 Jul 25 '17 at 9:54
• @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: 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 Jul 25 '17 at 12:42

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.

• 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 Jul 25 '17 at 4:40
• 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 Jul 25 '17 at 9:58
• 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 Jul 25 '17 at 20:17
• @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 Jul 26 '17 at 2:53