Bidirectional Search for Longest Paths: Case for Front-to-Front Heuristics
This work provides an incremental improvement in search efficiency for researchers and practitioners working on complex longest-path problems, particularly those with overlapping constraints.
This paper introduces BiXDFBnB, a bidirectional depth-first branch-and-bound algorithm for Generalized Longest Simple Path (GLSP) problems. It adapts the Single-Frontier Bidirectional Search framework to maximization problems, enabling efficient front-to-front heuristic evaluation without typical overhead, and shows improved node expansions and, in some cases, runtime for longest-path problems.
Bidirectional heuristic search can potentially reduce search effort for problems amenable to backward search. Therein, it is well-known that front-to-front heuristics can reduce the number of node expansions, but their overhead is so high that overall runtime almost always increases. We propose BiXDFBnB, a bidirectional depth-first branch-and-bound algorithm that adapts the Single-Frontier Bidirectional Search (SFBDS) framework - originally developed for shortest-path (MIN) problems - to the Generalized Longest Simple Path (GLSP) setting. Because SFBDS inherently operates on paired states, front-to-front (F2F) heuristic evaluation arises naturally and avoids the overhead typically associated with bidirectional frontier management. We show that this adaptation can be successfully applied to maximization (MAX) problems while efficiently handling overlapping constraints. BiXDFBnB is applied to several types of longest-path problems: Longest Simple Path (LSP), Snakes, and Coil-in-the-Box (CIB). Empirical evaluation shows that the new algorithm frequently reduces the number of node expansions and, in some cases, also improves overall runtime.