Before revision:  We settle this question by proving that computing \lambda_\infty is indeed NP-hard . Additionally, we use our techniques to prove NP-hardness of computing the spread constant (of a graph) \emph{  , a geometric measure  introduced by Alon, Boppana, and Spencer, in the context of deriving an asymptotic isoperimetric inequality on cartesian products of graphs.
After revision:  We settle this question by proving that computing \lambda_\infty is indeed NP-hard , even for weighted trees. Our gadget further proves NP-hardness of computing the spread constant (of a graph) \emph{ , a geometric measure introduced by Alon, Boppana, and Spencer, in the context of deriving an asymptotic isoperimetric inequality on cartesian products of graphs.