Fully Leafed Induced Subtrees

We consider the problem \(\mathrm {LIS}\) of deciding whether there exists an induced subtree with exactly \(i \le n\) vertices and \(\ell \) leaves in a given graph G with n vertices. We study the associated optimization problem, that consists in computing the maximal number of leaves, denoted by \(L_G(i)\), realized by an induced subtree with i vertices, for \(0 \le i \le n\). We begin by proving that the \(\mathrm {LIS}\) problem is NP-complete in general. Then, we describe a nontrivial branch and bound algorithm that computes the function \(L_G\) for any simple graph G. In the special case where G is a tree of maximum degree \(\varDelta \), we provide a \(\mathcal {O}(n^3\varDelta )\) time and \(\mathcal {O}(n^2)\) space algorithm to compute the function \(L_G\).