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.

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

Your Answer

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

Browse other questions tagged or ask your own question.