NP-hardness of a scheduling problem

Problem: Given an undirected, weighted, complete graph $G = (V, E, w, c)$. $w$ is the time weight function on edges, $w:E \to \mathbb{N}^{+}$; $w(e)$ represents the time it takes to travel along edge $e$. $c$ is the time deadline function on vertices, $c:V \to \mathbb{N}^{+}$.

Given a source vertex $s$, the question is whether there exists a tour $p: v_{0} = s \to^{e_{0}} v_{1} \to^{e^{1}} v_{2} \to \cdots \to v_{i} \to^{e_{i}} \to \cdots$ such that

• $\{ v_{i} \}$ is a multi-set. That is, $p$ is not necessarily a simple path.

• $\{ v_{i} \}$ contains all vertices, i.e., $V \subseteq \{ v_{i} \}$.

• For each vertex $v \in V$, suppose that it first appears in $p$ as $v_{i}$, then we require that

$$\sum_{n=0}^{n=i-1} w(e_{n}) \le c(v).$$

Background: A courier needs to deliver goods to the places represented by $V$. Each consignee has specified a deadline. The question is whether there is a tour satisfying all these deadlines.

I guess that this problem is NP-hard, and it reminds me of the scheduling problems with deadlines. However, I cannot find a suitable one for the reduction. Any ideas? (Other reductions for NP-hardness or algorithms are also appreciated.)

This sounds very much like a Hamilton path problem. If you set the edge weights all to $1$ and the deadline of the vertices all to $|V| - 1$, then each vertex can only be visited once, since there is not enough time to visit one twice before the deadline runs out. Finding a Hamilton path on the other hand is NP-hard. Thus, your problem is NP-hard as well.

StackExchange Computer Science Q#47506, answer score: 4