Bidirectional Heuristic Search in Longest Path Problems (Extended Abstract)

Abstract

Bidirectional heuristic search has the potential to decrease search time in combinatorial search problems amenable to backward search. To date, bidirectional search has been limited to minimization or shortest path problems. This paper extends the notion of bidirectional heuristic search to (constrained) longest path problems, which turns out to be non-trivial due to the path necessarily being part of the state and the inapplicability of standard bidirectional heuristic search techniques such as meet-in-the-middle (MM) and BAE*. We present a basic bidirectional heuristic search for longest simple path (LSP) in undirected graphs, and prove its correctness. We then suggest several refinements and optimizations, as well as a generalization to other types of longest path problems Coil-in-a-box (CIB). Empirical evaluation shows that, as with many forms of bidirectional search, sometimes unidirectional search wins, but for a sizable chunk of problem instance types, bidirectional search performs better by expanding fewer nodes and achieves a shorter runtime despite the increased overhead per expansion.