Steiner Tree Parameterized by Multiway Cut and Even Less

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 ^|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| ⁾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 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 ⁾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.