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

• URL: http://arxiv.org/abs/2606.05956v1
• Date: Thu, 04 Jun 2026 09:53:18 GMT
• Title: Bidirectional Search for Longest Paths: Case for Front-to-Front Heuristics
• Abstract summary: We propose BiXDFBnB, a bidirectional depth-first branch-and-bound algorithm that adapts the Single-Frontier Bidirectional Search framework.<n>Because SFBDS operates on paired states, front-to-front avoids the overhead typically associated with bidirectional frontier management.<n>BiXDFBnB is applied to several types of longest-path problems: Longest Simple Path (LSP), Snakes, and Coil-in-the-Box (CIB)
• Score: 5.729787815551408
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• 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.

Related papers

• Bidirectional Incremental Generalized Hybrid A* [5.811502603310249]
  We show that Bi-IGHA* substantially reduces expansions on R3, R4, and R6 planning problems.<n>We also show that Bi-IGHA* achieves equivalent closed-loop performance with kinodynamic planning for high-speed off-road autonomy.
  arXiv  Detail & Related papers  (2026-05-28T23:04:37Z)
• A*-Thought: Efficient Reasoning via Bidirectional Compression for Low-Resource Settings [60.48717743667377]
  A*-Thought is an efficient tree search-based unified framework designed to identify and isolate the most essential thoughts.<n>It formulates the reasoning process of LRMs as a search tree, where each node represents a reasoning span in the giant reasoning space.<n>It can improve the performance of QwQ-32B by 2.39$times$ with low-budget and reduce the length of the output token by nearly 50% with high-budget.
  arXiv  Detail & Related papers  (2025-05-30T12:58:34Z)
• Dynamic Parallel Tree Search for Efficient LLM Reasoning [102.16694475391665]
  Tree of Thoughts (ToT) enhances Large Language Model (LLM) reasoning by structuring problem-solving as a spanning tree.<n>We propose Dynamic Parallel Tree Search (DPTS), a novel parallelism framework that aims to dynamically optimize the reasoning path in inference.<n> Experiments on Qwen-2.5 and Llama-3 with Math500 and GSM8K datasets show that DPTS significantly improves efficiency by 2-4x on average.
  arXiv  Detail & Related papers  (2025-02-22T14:13:37Z)
• Dual-Branch HNSW Approach with Skip Bridges and LID-Driven Optimization [0.8786066051474574]
  The Hierarchical Navigable Small World (HNSW) algorithm is widely used for approximate nearest neighbor search.<n>We propose a novel algorithm that mitigates local optima and cluster disconnections while enhancing the construction speed, maintaining inference speed.<n> Experiments on various benchmarks and datasets showed that our algorithm outperforms the original HNSW in both accuracy and speed.
  arXiv  Detail & Related papers  (2025-01-23T10:20:12Z)
• Pathfinding with Lazy Successor Generation [12.02023514105999]
  We study a pathfinding problem where only locations are given, and edges are implicitly defined. Despite its simple structure, this problem becomes non-trivial with a massive number of locations. We propose a novel LaCAS* algorithm, which does not generate successors all at once but gradually generates successors as the search progresses.
  arXiv  Detail & Related papers  (2024-08-27T23:25:25Z)
• SLOPE: Search with Learned Optimal Pruning-based Expansion [2.0618817976970103]
  We present the Search with Learned Optimal Pruning-based Expansion (SLOPE) It learns the distance of a node from a possible optimal path, which in turn reduces the size of the open list. This ensures that the search explores only the region close to optimal paths while lowering memory and computational costs.
  arXiv  Detail & Related papers  (2024-06-07T13:42:15Z)
• Pseudonorm Approachability and Applications to Regret Minimization [73.54127663296906]
  We convert high-dimensional $ell_infty$-approachability problems to low-dimensional pseudonorm approachability problems. We develop an algorithmic theory of pseudonorm approachability, analogous to previous work on approachability for $ell$ and other norms.
  arXiv  Detail & Related papers  (2023-02-03T03:19:14Z)
• SoftTreeMax: Policy Gradient with Tree Search [72.9513807133171]
  We introduce SoftTreeMax, the first approach that integrates tree-search into policy gradient. On Atari, SoftTreeMax demonstrates up to 5x better performance in faster run-time compared with distributed PPO.
  arXiv  Detail & Related papers  (2022-09-28T09:55:47Z)
• Enhanced Methods for the Weight Constrained Shortest Path Problem [18.567812400186092]
  The Weight Constrained Shortest Path Problem (WCSPP) is a well-studied, yet challenging, topic in AI. This paper presents two new solution approaches to the WCSPP on the basis of A* search. We empirically evaluate the performance of our algorithms on a set of large and realistic problem instances.
  arXiv  Detail & Related papers  (2022-07-29T15:32:45Z)
• Towards Optimally Efficient Tree Search with Deep Learning [76.64632985696237]
  This paper investigates the classical integer least-squares problem which estimates signals integer from linear models. The problem is NP-hard and often arises in diverse applications such as signal processing, bioinformatics, communications and machine learning. We propose a general hyper-accelerated tree search (HATS) algorithm by employing a deep neural network to estimate the optimal estimation for the underlying simplified memory-bounded A* algorithm.
  arXiv  Detail & Related papers  (2021-01-07T08:00:02Z)
• Learning to Accelerate Heuristic Searching for Large-Scale Maximum Weighted b-Matching Problems in Online Advertising [51.97494906131859]
  Bipartite b-matching is fundamental in algorithm design, and has been widely applied into economic markets, labor markets, etc. Existing exact and approximate algorithms usually fail in such settings due to either requiring intolerable running time or too much computation resource. We propose textttNeuSearcher which leverages the knowledge learned from previously instances to solve new problem instances.
  arXiv  Detail & Related papers  (2020-05-09T02:48:23Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.