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$ Jan 3, 2012 at 18:23
  • $\begingroup$ @Jukka Suomela I thought about having a total order on the vertices. $\endgroup$
    – alex
    Jan 3, 2012 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$ Jan 3, 2012 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, 2012 at 22:46
  • $\begingroup$ @MarekChrobak that's just another formulation of knapsack problem =) $\endgroup$ Jan 14, 2012 at 18:13


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Browse other questions tagged or ask your own question.