Fully leafed induced subtrees

DOI10.1007/978-3-319-94667-2_8MaRDI QIDQ6291891arXivFDO

Authors Alexandre Blondin Massé, Julien de Carufel, Alain Goupil, Mélodie Lapointe, Émile Nadeau, Élise Vandomme

Publication date 28 September 2017

Published in arXiv

Full work available at URL https://doi.org/10.1007/978-3-319-94667-2_8

Mathematics Subject Classification ID

Trees (05C05) Enumeration in graph theory (05C30) Graph algorithms (graph-theoretic aspects) (05C85) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)

arXiv classification

cs.DSmath.CO

Abstract: Let $G$ be a simple graph on $n$ vertices. We consider the problem LIS of deciding whether there exists an induced subtree with exactly $ileqn$ 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 $0leilen$. 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 $2leqdleq6$. 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 $mathcalO(n^{3}Delta)$ time and $mathcalO(n^2)$ space algorithm to compute the function $L_G$.

This page was built for publication: Fully leafed induced subtrees

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6291891)