Exact question

Can few omissions be handled in FPT time?

A digraph is semicomplete when every pair of distinct vertices is joined by at least one directed arc. Given such a digraph$D$, distinct vertices$x,y$, and an integer$r\ge 0$, decide whether there is a directed $(x,y)$-path omitting at most $r$ vertices.

$$\text{Target running time: } f(r)n^{O(1)}.$$

Bai, Yan, and Zhou state this as Problem 5.4. Their exact algorithm enumerates all deletion sets of size at most$r$ and is XP, with an$n^{O(r)}$ factor. The paper explicitly leaves fixed-parameter tractability open.

Structural frontier

A path can be closed through one prescribed arc

Adding the arc $yx$ turns an$(x,y)$-path into a directed cycle through that arc without changing its vertex set. Thus the problem is equivalent to finding a cycle through one prescribed arc that omits at most $r$vertices.

The same authors prove that, in a strong semicomplete digraph, the vertices omitted by a longest prescribed-endpoint path, together with the endpoints, admit a Hamiltonian path in the reverse endpoint direction. This complementary path is strong structure, but known two-linkage algorithms do not directly optimize the number of vertices assigned to it.

Rejected route

Why iterative compression was the wrong first move

The proposed compression chose one Hamiltonian core path$P$, although the same instance may have many such paths and many equivalent witness orderings. It then proposed to measure deleted vertices and forward intervals relative to that choice.

That makes the proposed interval count presentation-dependent. Extending the census would chiefly classify combinations of path presentations and residual deletion sets. Without a canonical quotient that collapses those choices first, an exact local result would not supply a bridge to the global FPT question.

Preserved calibration

The census diagnoses the scale of the residual space

An exact census covers all$3^{10}=59{,}049$ labelled semicomplete digraphs on five vertices and all twenty ordered endpoint pairs. Among the 51,969 strong digraphs, the 1,039,380 endpoint instances have minimum-omission counts

$$r=0:800{,}220,\quad r=1:135{,}360,\quad r=2:51{,}120,\quad r=3:52{,}680.$$

This remains an exact control, not evidence for an asymptotic theorem. In the withdrawal audit, its main lesson is that the residual layers are already richly populated at the smallest nontrivial order.

Selection lesson

Prefer invariants that collapse presentations

Future hunts reject a candidate when its first serious move chooses an arbitrary witness or decomposition and then classifies the residual cases created by that choice. Multiple presentations can instead be the opportunity when one exact translation exposes a hidden invariant. The replacement must have a canonical object or a sharply defined representation bridge tied directly to the frontier.

Fold-and-Look origami is the positive control. Its bounded causal one-hinge geometry admitted a mirror-collision invariant that collapsed the image to a one-turn pushdown computation. The proof compressed presentations instead of inventorying them. Mathematical and theoretical physics are in scope for the next hunt, especially where gauge, geometric, operator, or moduli-space formulations have not yet been connected by an exact theorem. A particularly strong target will expose dynamics flattened by a symmetry quotient—such as boundary, defect, causal, or transverse-jet data—and distinguish it invariantly from pure gauge redundancy.

Sources and credit

• H. Bai, J. Yan, and J. Zhou, “Paths with Prescribed Endpoints in Semicomplete and Locally Semicomplete Digraphs” (2026)— formal source for the open problem, XP bound, complementary path theorem, and prescribed-arc reformulation.
• J. Bang-Jensen and C. Thomassen, “A Polynomial Algorithm for the 2-Path Problem for Semicomplete Digraphs”— background linkage algorithm; not by itself a solution of the optimization problem attacked here.