Tzur Shubi, Solomon Eyal Shimony, Ariel Felner, Shahaf Shperberg

Bidirectional Heuristic Search in Longest Path Problems (Extended Abstract)

Introduction

Bidirectional heuristic search in longest path problems (extended abstract). Extend bidirectional heuristic search to longest path problems, a non-trivial challenge previously limited to shortest paths. Explore LSP in undirected graphs, proving correctness & showing empirical benefits.

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.

Review

This extended abstract presents a highly significant contribution to the field of combinatorial search by pioneering the application of bidirectional heuristic search to longest path problems. Historically, bidirectional search techniques have been almost exclusively confined to minimization or shortest path scenarios, making this extension a non-trivial and welcome advancement. The authors correctly identify the inherent complexities, particularly the path-dependent nature of the state and the inapplicability of standard meet-in-the-middle or BAE* methods, which underscores the novelty and challenge of their endeavor. This work effectively addresses a critical gap in the literature, opening new avenues for efficient search in a different class of optimization problems. The technical core of the paper introduces a basic bidirectional heuristic search algorithm specifically tailored for the longest simple path (LSP) problem in undirected graphs, accompanied by a proof of correctness. This foundational work is then expanded upon with suggestions for several refinements, optimizations, and a crucial generalization to other complex longest path problems, such as Coil-in-a-box (CIB). The methodology appears sound in tackling the unique challenges of longest path problems, where the goal is maximization rather than minimization, and the intermediate path structure is critical. The proposed techniques demonstrate a thoughtful adaptation of bidirectional search principles to this distinct problem domain. Empirical evaluation, while presented succinctly in this extended abstract, indicates promising results. The findings suggest that, consistent with many applications of bidirectional search, performance can vary; unidirectional search sometimes prevails. However, for a "sizable chunk" of problem instance types, the proposed bidirectional approach demonstrably outperforms its unidirectional counterpart by expanding fewer nodes and achieving a shorter runtime. This is particularly noteworthy given the acknowledged increase in overhead per expansion, implying that the reduction in search space is substantial enough to offset the added computational cost. This work lays a strong foundation and demonstrates the practical utility of bidirectional heuristic search in a previously unexplored and challenging problem space.

Full Text

Comments

You need to be logged in to post a comment.