Abstract
In 2010 Bjorklund [FOCS'10] published a surprising result, which states that Hamiltonian cycles in undirected graphs can be found in 1.66^n time, breaking the 2^n barrier. It was soon extended by Bjorklund, Husfeldt, Kaski and Koivisto to an algorithm that finds a path of length k in 1.66^k n^{O(1)} running time.
Raible et al [Algorithmica'13] posed an open problem whether the approach of Bjorklund et al extends to finding trees of size k. In this work we show that the answer to this question is positive, provided that we restrict ourselves to trees with few leaves, namely, we show an algorithm running in time 1.66^k * 2^{l/2} n^{O(1)}, where l is the number of leaves. This has further consequences for the k-internal spanning tree problem, including breaking the 2^n running time barrier.
Moreover, the Hamiltonicity problem was known to be easier when the input graph has low maximum degree (Eppstein [JGAA'07], Gebauer [ANALCO'08]). It is natural to ask whether the approach of Bjorklund et al can also get more efficient in these restricted cases. We give a positive answer, through the more general setting of vertex colored graphs. It turns out that, apart from the ordinary proper vertex coloring, also applying fractional coloring or vector coloring gives improved running time bounds in some graph classes.
Joint work with Andreas Bjorklund, Vikram Kamat and Meirav Zehavi.