Fully Leafed Induced Subtrees

摘要

We consider the problem LIS of deciding whether there exists an induced subtree with exactly i ≤ n vertices and ?. 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 ≤ i ≤ n. We begin by proving that the 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 A, we provide a O(n~3△) time and O(n~2) space algorithm to compute the function L_G.