Max weight travel on a graph with deadline

Question

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

Answer 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.