2014/03/01 by Hadas Shachnai, Meirav Zehavi, Shachnai, Hadas +1
Computer Science · Engineering · #Advanced Graph Theory Research #Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences #Optimization and Packing Problems #VLSI and FPGA Design Techniques
paper · pdf · doi:10.48550/arxiv.1403.0099
openalex publication_date 2014/03/01 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
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 α1m1 + α2m2 is at most (or at least) p, where α1,α2∈ℝ are constants defining the problem, and m1, m2 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^*(4k+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^*(4p+o(p)) time algorithm for Max (k,n-k)-Cut, thus improving significantly the best known O^*(pp) time algorithm.