Conditional subexponential algorithms for sparse connectivity problems

Assume the Boolean tensor-contraction algorithm in Appendix D of OpenAI's25 October 2026 preprint is correct. We show that the standard Cut\&Countconstructions then yield randomized algorithms taking\(2^{O((n+m)/\sqrt{\log(n+m+2)})}\) time and polynomial space forHamiltonicity, undirected Feedback Vertex Set, unweighted Steiner Tree, ConnectedVertex Cover, and Connected Dominating Set. The same bound covers longestpaths and cycles, leaf-constrained spanning trees, and polynomially weightedtravelling-salesman problems on sparse graphs. No maximum-degree bound isneeded. Hamiltonian-cycle and Hamiltonian-path parity, in both directed andundirected graphs, can be computed deterministically. We give the detailsof the transfer, including a coefficient-degree extension of the contractionalgorithm and linear-size encodings of high-degree constraints. The parityarguments are established methods; the conclusion is their conditionalapplication to the new contraction bound.