View article

To determine if a graph has a spanning tree with few leaves is NP-hard. In this paper we study the parametric dual of this problem, k-Internal Spanning Tree (Does G have a spanning tree with at least k internal vertices?). We give an algorithm running in time O(2^4klogk ·k ^7/2 + k ² ·n ²). We also give a 2-approximation algorithm for the problem.

However, the main contribution of this paper is that we show the following remarkable structural bindings between k-Internal Spanning Tree and k-Vertex Cover:

• No for k-Vertex Cover implies Yes for k-Internal Spanning Tree.
• Yes for k-Vertex Cover implies No for (2k+1)-Internal Spanning Tree.

We give a polynomial-time algorithm that produces either a vertex cover of size kor a spanning tree with …