Endpoint Conversion for Graphic s-t Path TSP on Cubic Graphs

We study the fixed-endpoint graphic s-t path TSP on simple cubic graphs. Building on the edge-conditioned even-cover theorem of Wigal, Yoo, and Yu for cubic-tour walks, we prove an endpoint-conversion theorem: if G is simple, cubic, and 2-vertex-connected, and if either st is an edge of G or G - s, t is connected, then OPT (G, s, t) = n - 1 yields an asymptotic path Held-Karp gap upper bound of 5/4. We also prove an adjacent-terminal LP certificate with value exactly n - 1; combined with the Lukotka-Mazak cubic tour lower-bound family, this gives an asymptotic lower bound of 9/8. The coefficient 5/4 is tight for the broader 2-vertex-connected endpoint-conversion theorem, while the exact gap on the 3-edge-connected class remains open in 9/8, 5/4. An O (n²) -time algorithm constructs an s-t walk of length at most floor (5n/4).