MathDBBang–Jensen–Gutin Prescribed-Endpoint Path Problems
Bang–Jensen–Gutin Prescribed-Endpoint Path Problems
Given a semicomplete digraph and distinct vertices , determine a longest directed -path. Given a locally semicomplete digraph and distinct vertices , determine whether contains a Hamiltonian directed -path, that is, a directed path from to containing every vertex of exactly once. The general problem remains unresolved for strong, nonsemicomplete, non--strong locally semicomplete digraphs.
Progress summary
A 2026 paper settles several important special cases, but the full prescribed-endpoint path problem remains open for a broad class of directed networks.
The problem asks when directed graphs contain Hamiltonian or longest paths joining specified endpoints. The recent work by Bai, Hanzhi, Yan, Jin, Zhou, and Jia advances both questions through structural reductions.
August 2026 structural progress
The paper settles several structural cases in semicomplete and locally semicomplete digraphs and gives an equivalent cycle formulation. It explicitly leaves the strong, nonsemicomplete, non--strong case open.
Current status (as of August 2026): Several semicomplete and locally semicomplete cases are settled, while strong nonsemicomplete locally semicomplete digraphs remain unresolved.
Sources
Sources & referencesView supporting material
Primary source
Additional references
- Paths with Prescribed Endpoints in Semicomplete and Locally Semicomplete Digraphs — arXiv — Bai, Hanzhi, Yan, Jin, Zhou, Jia
Solutions 0
Sign in to submit a solution.
No solutions have been posted yet.