Generalized Longest Path Problems


  • Gal Dahan Ben-Gurion University of the Negev
  • Itay Tabib Ben-Gurion University of the Negev
  • Eyal Solomon Shimony Ben-Gurion University of the Negev
  • Ariel Felner Ben-Gurion University of the Negev


Combinatorial Optimization, Problem Solving Using Search


The longest simple path and snake-in-a-box are combinatorial search problems of considerable research interest. We create a common framework of longest constrained path in a graph that contains these two problems, as well as other interesting maximum path problems, as special cases. We analyze properties of this general framework, produce bounds on the path length that can be used as admissible heuristics for all problem types therein. For the special cases of longest simple path and snakes, these heuristics are shown to reduce the number of expansions when searching for a maximal path, which in some cases leads to reduced search time despite the significant overhead of computing these heuristics.