Many divide‐and‐conquer algorithms employ the fact that the vertex set of a graph of bounded treewidth can be separated in two roughly balanced subsets by removing a small subset of vertices, referred to as a separator. In this paper we prove a trade‐off between the size of the separator and the sharpness with which we can fix the size of the two sides of the partition. Our result appears to be a handy and powerful tool for the design of exact and parameterized algorithms for NP‐hard problems. We illustrate that by presenting two applications. Our first application is a O(2
n+o(n))‐time algorithm for the Degree Constrained Spanning Tree problem: find a spanning tree of a graph with the maximum number of nodes satisfying given degree constraints. This problem generalizes some well‐studied problems, among them Hamiltonian Path, Full Degree Spanning Tree, Bounded Degree Spanning Tree, and Maximum Internal Spanning Tree. The second application is a parameterized algorithm with running time O(16
k+o(k)+n
O(1)) for the k‐Internal Out‐Branching problem: here the goal is to compute an out‐branching of a digraph with at least k internal nodes. This is a significant improvement over the best previously known parameterized algorithm for the problem by Cohen et al. (2010), running in time O(49.4
k
+n
O(1)).
