<p>All the np-hard routing problems I know are of the form, minimize some quantity while visiting the verticies in an unordered way.</p>

<p>Are there problems which are still np-hard, if one has to visit the vertices in a given odering? </p>

<p>The only problem I can think of which partially falls into this is the 
"Vehicle routing problem with time windows problem" where the time window kind of dictates an order.</p>

CC BY-SA 3.0
2012-01-03T18:23:57.330Z
Do you mean that you are given a *total* order on vertices or a *partial* order on vertices?
Jukka Suomela
CC BY-SA 3.0
2012-01-03T19:21:08.313Z
@Jukka Suomela  I thought about having a total order on the vertices.
alex
CC BY-SA 3.0
2012-01-03T20:32:06.130Z
The problem needs to involve some kind of choice. For example, if you allow multiple edges between any pair of vertices, and weights, then it is NP-hard to determine if there is a way to visit vertices $1,2,...,n$, in this order, via a path of a specified total weight $W$.
Marek Chrobak
CC BY-SA 3.0
2012-01-03T22:46:33.197Z
moreover, assuming complexity theory conjectures, the search space created by those choices should probably be large (otherwise if checking is easy, by enumerating possible certificates one can solve the problem).
Kaveh
CC BY-SA 3.0
2012-01-14T18:13:27.787Z
@MarekChrobak that's just another formulation of knapsack problem =)
Dmytro Korduban
<cc.complexity-theory><np-hardness><tsp>
Ordered routing problem which is NP-hard
alex
# Ordered routing problem which is NP-hard

(Asked by: username_0 on 2012-01-03)

All the np-hard routing problems I know are of the form, minimize some quantity while visiting the verticies in an unordered way.

Are there problems which are still np-hard, if one has to visit the vertices in a given odering?

The only problem I can think of which partially falls into this is the
"Vehicle routing problem with time windows problem" where the time window kind of dictates an order.

**Tags:** cc.complexity-theory, np-hardness, tsp

> **Comments:**
> **username_1**: Do you mean that you are given a *total* order on vertices or a *partial* order on vertices?  
> **username_0**: @username_1  I thought about having a total order on the vertices.  
> **username_2**: The problem needs to involve some kind of choice. For example, if you allow multiple edges between any pair of vertices, and weights, then it is NP-hard to determine if there is a way to visit vertices $1,2,...,n$, in this order, via a path of a specified total weight $W$.  
> **username_3**: moreover, assuming complexity theory conjectures, the search space created by those choices should probably be large (otherwise if checking is easy, by enumerating possible certificates one can solve the problem).  
> **username_4**: @MarekChrobak that's just another formulation of knapsack problem =)  

---

## 0 answers

