3
$\begingroup$

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

$\endgroup$
4
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.