Parameterized Algorithms for Graph Partitioning Problems

Abstract

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 (FGPPs) 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)}\varDelta ^k)$ algorithm for any problem in this class, where $\varDelta \ge 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.