Bidirectional Search for Longest Paths: Case for Front-to-Front Heuristics

Tzur Shubi, Ariel Felner, Solomon Eyal Shimony, Shahaf S. ShperbergarXiv 2026 · arXiv

TL;DR

The paper introduces BiXDFBnB, a novel bidirectional depth-first branch-and-bound algorithm designed to solve Generalized Longest Simple Path (GLSP) problems. By adapting the Single-Frontier Bidirectional Search framework, the algorithm successfully leverages highly accurate front-to-front (F2F) heuristics without incurring the massive computational overhead that traditionally plagues them. The result is a highly efficient solver that reduces node expansions by orders of magnitude and significantly improves overall runtime on complex maximization problems.

What Problem Does This Paper Address?

Finding the shortest path in a graph is a foundational computer science problem with efficient solutions. Finding the longest simple path (LSP), however, is NP-hard and notoriously difficult to approximate. LSP and its variants (like the "Snake-in-the-box" problem) are critical for applications ranging from VLSI circuit design and multi-robot patrolling to optimizing error-correcting codes.

While bidirectional search—searching simultaneously forward from the start and backward from the goal—is highly effective for minimization (shortest path) problems, it struggles with maximization problems. In longest-path search, algorithms must rely on overestimating upper bounds rather than tight lower bounds, making it incredibly difficult to determine when the forward and backward search frontiers have safely met in the middle. Furthermore, maintaining and cross-referencing two separate search frontiers to prevent path overlaps introduces massive computational overhead, often making bidirectional search slower than simple unidirectional approaches.

Methods

To overcome these limitations, the authors present BiXDFBnB (Bidirectional Depth-First Branch-and-Bound). Instead of growing two independent frontiers, the algorithm adapts the Single-Frontier Bidirectional Search (SFBDS) framework to a maximization setting.

Key methodological innovations include:

  • Synchronized Paired States: Each node in the search tree represents exactly one pair of states: a forward path prefix and a backward path suffix. This eliminates the need to manage and match large, independent frontiers.
  • Simultaneous Expansion Paradigm: Instead of alternating directions, the algorithm expands both the forward and backward paths at the same time by generating the Cartesian product of their valid successors. This ensures that for graphs with unit edge weights, the frontiers mathematically "meet in the middle."
  • Overhead-Free Front-to-Front (F2F) Heuristics: Because the search operates on a single pair of states at any given time, computing a front-to-front heuristic simply requires evaluating the gap between the two current path heads. This completely bypasses the quadratic frontier-matching bottleneck typical of standard bidirectional architectures.
  • Parity and Overlap Handling: Simultaneous expansion guarantees that paths will either land on the exact same vertex (Exact Meet) or become adjacent (Adjacent Meet), preventing frontiers from illegally crossing each other undetected.

Datasets

The algorithm was evaluated across four challenging NP-hard combinatorial domains:

  1. LSP in Grids: 2D grids ranging from $6 \times 6$ to $8 \times 8$ with randomly placed obstacles at varying densities (8%, 12%, 16%, and 20%).
  2. Snake in Grids: Grid-based paths with strict induced-path constraints (no adjacent shortcuts allowed), tested on sizes from $7 \times 7$ to $9 \times 9$.
  3. LSP in Mazes: A base maze benchmark modified by clearing random diamond-shaped areas to create massive, open local state spaces.
  4. Coil-in-the-Box (CIB): Finding the longest constrained cycle in an $n$-dimensional hypercube, evaluated on dimensions 4D through 7D.

Key Insights and Ideas

  • The Power of Graph Fragmentation: Iteratively growing two opposing paths from the start and end points breaks apart the remaining graph topology far more aggressively than extending a single continuous path. Because advanced longest-path heuristics rely heavily on analyzing biconnected components, this severe topological fragmentation triggers much earlier and more effective heuristic cutoffs.
  • F2F vs. F2E Efficiency: Traditional front-to-end (F2E) heuristics evaluate the forward and backward paths independently, ignoring how the two paths block each other. F2F heuristics evaluate a single remaining graph constrained by both paths simultaneously, yielding significantly tighter and more accurate upper bounds.
  • Branch-and-Bound Beats Best-First Memory Bottlenecks: Best-first bidirectional algorithms like XMM quickly run out of memory on hard problems due to exponential frontier growth. By utilizing a depth-first branch-and-bound strategy, BiXDFBnB maintains a linear memory footprint relative to search depth.

Key Results

The empirical evaluation demonstrated that upgrading from F2E to F2F heuristics within BiXDFBnB reduces node expansions by up to two orders of magnitude, directly translating into faster wall-clock runtimes.

Comparison between F2E and F2F variants

In the highly complex Coil-in-the-Box (CIB) domain, BiXDFBnB (F2F) demonstrated exceptional scalability. For a 7D hypercube, it successfully discovered the optimal path in just 56 seconds, whereas standard A* and the F2E variant failed to finish within a 12-hour time limit.

Figure 1: Coil-in-the-Box results. F2F’s expansion reduction (right) directly enables its runtime advantage (left).

Similarly, for the Snake in Grids domain, BiXDFBnB (F2F) consistently dominated all baselines across all obstacle densities, proving highly resilient as the problem difficulty scaled up (fewer obstacles create a larger search space).

Figure 2: Average and standard deviation of expansions for Snake in 8 × 8 Grids with varying obstacle densities.

Limitations and Future Work

While BiXDFBnB delivers impressive performance, the authors note a few areas for improvement:

  • Static Expansion Policy: The current implementation relies on a static, alternating policy to grow the forward and backward frontiers. Preliminary tests with dynamic "jumping" policies (like 1-step or double-lookahead) show potential for even fewer node expansions, though they currently introduce too much runtime overhead in higher dimensions.
  • Parallelization: The depth-first nature of the branch-and-bound framework makes it an excellent candidate for parallel processing architectures, which remains unexplored in this paper.
  • Scope of Constraints: The framework is currently tailored to GLSP problems; extending it to broader classes of constrained maximization problems is a task left for future research.

Summary updated

Abstract

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.
BibTeX
@misc{shubi2026bidirectional,
  author = {Tzur Shubi and Ariel Felner and Solomon Eyal Shimony and Shahaf S. Shperberg},
  title = {{Bidirectional Search for Longest Paths: Case for Front-to-Front Heuristics}},
  year = {2026},
  eprint = {2606.05956},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2606.05956},
}

Loading related content...

Figure