Prof. Meirav Zehavi

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 ⊆ V of size k, such that α₁m₁ + α₂m₂ is at most (or at least) p, where α₁, α₂ ∈ R are constants defining the problem, and m₁,m₂ 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)Δk) algorithm for any problem in this class, where Δ ≥ 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.