  Given a graph $G = (V, E)$ and an integer $k$, we study $k$-Vertex Seperator
(resp. $k$-Edge Separator), where the goal is to remove the minimum number of
vertices (resp. edges) such that each connected component in the resulting
graph has at most $k$ vertices. Our primary focus is on the case where $k$ is
either a constant or a slowly growing function of $n$ (e.g. $O(\log n)$ or
$n^{o(1)}$). Our problems can be interpreted as a special case of three general
classes of problems that have been studied separately (balanced graph
partitioning, Hypergraph Vertex Cover (HVC), and fixed parameter tractability
(FPT)).
  Our main result is an $O(\log k)$-approximation algorithm for $k$-Vertex
Seperator that runs in time $2^{O(k)} n^{O(1)}$, and an $O(\log
k)$-approximation algorithm for $k$-Edge Separator that runs in time
$n^{O(1)}$. Our result on $k$-Edge Seperator improves the best previous graph
partitioning algorithm for small $k$. Our result on $k$-Vertex Seperator
improves the simple $(k+1)$-approximation from HVC. When $OPT > k$, the running
time $2^{O(k)} n^{O(1)}$ is faster than the lower bound $k^{\Omega(OPT)}
n^{\Omega(1)}$ for exact algorithms assuming the Exponential Time Hypothesis.
While the running time of $2^{O(k)} n^{O(1)}$ for $k$-Vertex Separator seems
unsatisfactory, we show that the superpolynomial dependence on $k$ may be
needed to achieve a polylogarithmic approximation ratio, based on hardness of
Densest $k$-Subgraph.
  We also study $k$-Path Transversal, where the goal is to remove the minimum
number of vertices such that there is no simple path of length $k$. With
additional ideas from FPT algorithms and graph theory, we present an $O(\log
k)$-approximation algorithm for $k$-Path Transversal that runs in time
$2^{O(k^3 \log k)} n^{O(1)}$. Previously, the existence of even $(1 -
\delta)k$-approximation algorithm for fixed $\delta > 0$ was open.
