# Ordered routing problem which is NP-hard

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.

• Do you mean that you are given a total order on vertices or a partial order on vertices? – Jukka Suomela Jan 3 '12 at 18:23
• @Jukka Suomela I thought about having a total order on the vertices. – alex Jan 3 '12 at 19:21
• 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 Jan 3 '12 at 20:32
• 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 Jan 3 '12 at 22:46
• @MarekChrobak that's just another formulation of knapsack problem =) – Dmytro Korduban Jan 14 '12 at 18:13