Solving Hamiltonian Cycle by an EPT algorithm for a non-sparse parameter

Recently, it was shown that Hamiltonian Cycle parameterized by treewidth is in EPT (Bodlaender et al., 2013; Fomin et al., 2014), meaning it can be solved in nO(1)2O(k)-time. In this paper, using tools from Fomin et al. (2014), we show that also parameterized by split-matching-width Hamiltonian Cycle is EPT. To the best of our knowledge, this is the first EPT algorithm for any “globally constrained” graph problem parameterized by a non-trivial and non-sparse structural parameter. To accomplish this, we also give an algorithm constructing a branch decomposition approximating the minimum split-matching-width to within a constant factor. Combined, these results show that the algorithms in Sæther and Telle (2016) for Edge Dominating Set, Chromatic Number and Max Cut all can be improved. In fact, using our new approximation algorithm, under the Exponential Time Hypothesis, the Hamiltonian Cycle algorithm of this paper, and the three algorithms for MaxCut, Edge Dominating Set, and Chromatic Number, are asymptotically optimal.