  We study a broad class of graph partitioning problems, where each problem is
specified by a graph $G=(V,E)$, and parameters $k$ and $p$. We seek a subset
$U\subseteq V$ of size $k$, such that $\alpha_1m_1 + \alpha_2m_2$ is at most
(or at least) $p$, where $\alpha_1,\alpha_2\in\mathbb{R}$ are constants
defining the problem, and $m_1, m_2$ are the cardinalities of the edge sets
having both endpoints, and exactly one endpoint, in $U$, respectively. This
class of fixed cardinality graph partitioning problems (FGPP) encompasses Max
$(k,n-k)$-Cut, Min $k$-Vertex Cover, $k$-Densest Subgraph, and $k$-Sparsest
Subgraph.
  Our main result is an $O^*(4^{k+o(k)}\Delta^k)$ algorithm for any problem in
this class, where $\Delta \geq 1$ is the maximum degree in the input graph.
This resolves an open question posed by Bonnet et al. [IPEC 2013]. We obtain
faster algorithms for certain subclasses of FGPPs, parameterized by $p$, or by
$(k+p)$. In particular, we give an $O^*(4^{p+o(p)})$ time algorithm for Max
$(k,n-k)$-Cut, thus improving significantly the best known $O^*(p^p)$ time
algorithm.

Data Structures and Algorithms