Exact Exponential Time Algorithms for Max Internal Spanning Tree

2008/11/12 by Henning Fernau, Fernau, Henning, Serge Gaspers +3
Computer Science · #Advanced Graph Theory Research #Algorithms and Data Compression #Data Structures and Algorithms (cs.DS) #Discrete Mathematics (cs.DM) #FOS: Computer and information sciences #cs.DM #cs.DS #semigroups and automata theory

paper · pdf · doi:10.48550/arxiv.0811.1875

openalex publication_date 2008/11/12 · arxiv created 2009/06/12 · arxiv updated 2009/12/01 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

Abstract

We consider the 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 O*(cⁿ) (c <= 3). 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 O*(1.8669ⁿ) when analyzed with respect to the number of vertices. We also show that its running time is 2.1364^k n^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 analyses for parameterized algorithms.

Related

• Algorithms for Maximum Internal Spanning Tree Problem for Some Graph Classes
• A 4/3-approximation algorithm for finding a spanning tree to maximize its internal vertices
• A Faster Exact Algorithm for the Directed Maximum Leaf Spanning Tree Problem
• An Approximation Algorithm for Maximum Internal Spanning Tree
• A Linear Vertex Kernel for Maximum Internal Spanning Tree