  In the Steiner Tree problem we are given an undirected edge-weighted graph as
input, along with a set $K$ of vertices called terminals. The task is to output
a minimum-weight connected subgraph that spans all the terminals. The famous
Dreyfus-Wagner algorithm running in $3^{|K|} \mathsf{poly}(n)$ time shows that
the problem is fixed-parameter tractable parameterized by the number of
terminals. We present fixed-parameter tractable algorithms for Steiner Tree
using structurally smaller parameterizations.
  Our first result concerns the parameterization by a multiway cut $S$ of the
terminals, which is a vertex set $S$ (possibly containing terminals) such that
each connected component of $G-S$ contains at most one terminal. We show that
Steiner Tree can be solved in $2^{O(|S|\log|S|)}\mathsf{poly}(n)$ time and
polynomial space, where $S$ is a minimum multiway cut for $K$. The algorithm is
based on the insight that, after guessing how an optimal Steiner tree interacts
with a multiway cut $S$, computing a minimum-cost solution of this type can be
formulated as minimum-cost bipartite matching.
  Our second result concerns a new hybrid parameterization called $K$-free
treewidth that simultaneously refines the number of terminals $|K|$ and the
treewidth of the input graph. By utilizing recent work on
$\mathcal{H}$-Treewidth in order to find a corresponding decomposition of the
graph, we give an algorithm that solves Steiner Tree in time $2^{O(k)}
\mathsf{poly}(n)$, where $k$ denotes the $K$-free treewidth of the input graph.
To obtain this running time, we show how the rank-based approach for solving
Steiner Tree parameterized by treewidth can be extended to work in the setting
of $K$-free treewidth, by exploiting existing algorithms parameterized by $|K|$
to compute the table entries of leaf bags of a tree $K$-free decomposition.
