An exact algorithm for TSP in degree-3 graphs via circuit procedure and amortization on connectivity structure (Q262259)

The authors present a deterministic algorithm for TSP in degree-3 graphs, which runs in \(O^*(2^{\frac3{10}n})= O^*(1.2312^n)\) time and polynomial space. This improves the previous time bounds of \(O^*(1.251^n)\) by Iwama and Nakashima and \(O(1.260^n)\) by Eppstein. The algorithm is simple and contains only one branch rule (include/exclude edge) that is designed on a cut-circuit structure of a graph induced by unprocessed edges. The crucial point of the paper is the application of the measure and conquer method to analyze the running time. An amortization scheme over the cut-circuit structure of graphs is invented, wherein the authors introduce not only weights of vertices but also weights of \(U\)-components to define the measure of an instance. The idea of amortization schemes introducing weights on components may yield better bounds for other exact algorithms for graph problems when it is successfully analyzed how reduction/ branching procedures change the system of components.