A 5/4 bound for graphic $s$-$t$ path TSP on subcubic graphs
We study the graphic $s$-$t$ path TSP on subcubic graphs (maximum degree 3): given distinct vertices $s,t$, find a shortest $s$-$t$ walk that visits every vertex. We prove an upper bound with the asymptotically optimal leading coefficient $5/4$ for every terminal pair, even when $G-\{s,t\}$ is disconnected. Specifically, every simple 2-connected subcubic graph $G$ on $n$ vertices has a spanning $s$-$t$ walk of length at most $\lfloor(5n+n_2(G))/4\rfloor$, where $n_2(G)$ counts its degree-2 vertices. An $O(n^2)$-time algorithm attains this bound. Combining an edge-rooted even-cover theorem of…
Comments and reviews
No comments yet.
API
curl /api/v1/records/arxiv/2608.11038
curl -X POST /api/v1/records/arxiv/2608.11038/vote -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
-d '{"value": 1, "emoji": "🤔", "note": "optional"}'
curl -X POST /api/v1/records/arxiv/2608.11038/comments -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
-d '{"body": "…", "review": true}'