  Let $G$ be a simple graph on $n$ vertices. We consider the problem LIS of
deciding whether there exists an induced subtree with exactly $i \leq n$
vertices and $\ell$ leaves in $G$. 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 LIS problem is NP-complete in general and then
we compute the values of the map $L_G$ for some classical families of graphs
and in particular for the $d$-dimensional hypercubic graphs $Q_d$, for $2 \leq
d \leq 6$. We also 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 $\Delta$, we provide a $\mathcal{O}(n^3\Delta)$
time and $\mathcal{O}(n^2)$ space algorithm to compute the function $L_G$.
