  In algorithmic graph theory, a classic open question is to determine the
complexity of the Maximum Independent Set problem on $P_t$-free graphs, that
is, on graphs not containing any induced path on $t$ vertices. So far,
polynomial-time algorithms are known only for $t\le 5$ [Lokshtanov et al., SODA
2014, 570--581, 2014], and an algorithm for $t=6$ announced recently [Grzesik
et al. Arxiv 1707.05491, 2017]. Here we study the existence of
subexponential-time algorithms for the problem: we show that for any $t\ge 1$,
there is an algorithm for Maximum Independent Set on $P_t$-free graphs whose
running time is subexponential in the number of vertices. Even for the weighted
version MWIS, the problem is solvable in $2^{O(\sqrt {tn \log n})}$ time on
$P_t$-free graphs. For approximation of MIS in broom-free graphs, a similar
time bound is proved.
  Scattered Set is the generalization of Maximum Independent Set where the
vertices of the solution are required to be at distance at least $d$ from each
other. We give a complete characterization of those graphs $H$ for which
$d$-Scattered Set on $H$-free graphs can be solved in time subexponential in
the size of the input (that is, in the number of vertices plus the number of
edges): If every component of $H$ is a path, then $d$-Scattered Set on $H$-free
graphs with $n$ vertices and $m$ edges can be solved in time
$2^{O(|V(H)|\sqrt{n+m}\log (n+m))}$, even if $d$ is part of the input.
Otherwise, assuming the Exponential-Time Hypothesis (ETH), there is no
$2^{o(n+m)}$-time algorithm for $d$-Scattered Set for any fixed $d\ge 3$ on
$H$-free graphs with $n$-vertices and $m$-edges.
