Junho Hwang

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 two vertices s, t, find a shortest walk from s to t that visits every vertex. Our main result is that the optimal 5/4 coefficient is attained for every terminal pair — including the difficult case wher...