Exact and Parameterized Algorithms for Max Internal Spanning Tree

We consider the $\mathrm{𝒩𝒫}$ ‐hard problem of finding a spanning tree with a maximum number of internal vertices. This problem is a generalization of the famous Hamiltonian Path problem. Our dynamic‐programming algorithms for general and degree‐bounded graphs have running times of the form ${𝒪}^{*}(c^n)$ with c≤2. For graphs with bounded degree, c <2. The main result, however, is a branching algorithm for graphs with maximum degree three. It only needs polynomial space and has a running time of $𝒪({1.8612}^n)$ when analyzed with respect to the number of vertices. We also show that its running time is ${2.1364}^k{n}^{𝒪(1)}$ when the goal is to find a spanning tree with at least k internal vertices. Both running time bounds are obtained via a Measure & Conquer analysis, the latter one being a novel use of this kind of analysis for parameterized algorithms.