Exact and Parameterized Algorithms for Max Internal Spanning Tree

• DOI: 10.1007/s00453-011-9575-5
• Publication Date: 2011-09-29T12:17:36Z
• Authors: Daniel Binkele-Ra...; Henning Fernau; Serge Gaspers; Mathieu Liedloff
• Keywords: Degree (music); Theory of computation

We consider the $\mathcal{NP}$-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 $\mathcal{O}^{*}(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 $\mathcal{O}(1.8612^{n})$ when analyzed with respect to the number of vertices. We also show that its running time is $2.1364^{k} n^{\mathcal{O}(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.