  The kTree problem is a special case of Subgraph Isomorphism where the pattern
graph is a tree, that is, the input is an $n$-node graph $G$ and a $k$-node
tree $T$, and the goal is to determine whether $G$ has a subgraph isomorphic to
$T$. We provide evidence that this problem cannot be computed significantly
faster than $2^{k} \textsf{poly}(n)$, which matches the fastest algorithm known
for this problem by Koutis and Williams [ICALP 2009 and TALG 2016].
Specifically, we show that if kTree can be solved in time $(2-\varepsilon)^k
\textsf{poly}(n)$ for some constant $\varepsilon>0$, then Set Cover with $n'$
elements and $m'$ sets can be solved in time $(2-\delta)^{n'}
\textsf{poly}(m')$ for a constant $\delta(\varepsilon) > 0$, which would refute
the Set Cover Conjecture by Cygan et al. [CCC 2012 and TALG 2016].
  Our techniques yield a new algorithm for the p-Partial Cover problem, a
parameterized version of Set Cover that requires covering at least $p$ elements
(rather than all elements). Its running time is $(2+\varepsilon)^p
(m')^{O(1/\varepsilon)}$ for any fixed $\varepsilon>0$, which improves the
previous $2.597^p \textsf{poly}(m')$-time algorithm by Zehavi [ESA 2015]. Our
running time is nearly optimal, as a $(2-\varepsilon')^p
\textsf{poly}(m')$-time algorithm would refute the Set Cover Conjecture.
