Min-Max Graph Partitioning and Small Set Expansion

DOI10.1137/120873996zbMATH Open1360.68639arXiv1110.4319OpenAlexW2179340953MaRDI QIDQ5494941FDOQ5494941

Authors: N. Bansal, Robert Krauthgamer, Konstantin Makarychev, Viswanath Nagarajan, Joseph (Seffi) Naor, Roy Schwartz, Uriel Feige 

Publication date: 30 July 2014

Published in: SIAM Journal on Computing (Search for Journal in Brave)

Abstract: We study graph partitioning problems from a min-max perspective, in which an input graph on n vertices should be partitioned into k parts, and the objective is to minimize the maximum number of edges leaving a single part. The two main versions we consider are where the k parts need to be of equal-size, and where they must separate a set of k given terminals. We consider a common generalization of these two problems, and design for it an $O(sqrtlognlogk)$-approximation algorithm. This improves over an $O(lo{g}^{2}n)$ approximation for the second version, and roughly $O(klogn)$ approximation for the first version that follows from other previous work. We also give an improved O(1)-approximation algorithm for graphs that exclude any fixed minor. Our algorithm uses a new procedure for solving the Small-Set Expansion problem. In this problem, we are given a graph G and the goal is to find a non-empty set $SsubseteqV$ of size $|S|leqhon$ with minimum edge-expansion. We give an $O(sqrtlognlog(1/ho))$ bicriteria approximation algorithm for the general case of Small-Set Expansion, and O(1) approximation algorithm for graphs that exclude any fixed minor.

Full work available at URL: https://arxiv.org/abs/1110.4319

Recommendations

• Graph partitions with minimum degree constraints
• scientific article; zbMATH DE number 1792660
• Minimizing the union: tight approximations for small set bipartite vertex expansion
• Min-max cover of a graph with a small number of parts
• Max-min partitioning of grid graphs into connected components
• On minimal arbitrarily partitionable graphs
• Minimum cost subpartitions in graphs
• Minimization and parameterized variants of vertex partition problems on graphs
• Partitions of graphs into small and large sets
• Partitioning a graph into minimum gap components

zbMATH Keywords

expansionbalanced cutspreading metricssparse cut

Mathematics Subject Classification ID

Graph algorithms (graph-theoretic aspects) (05C85) Graph theory (including graph drawing) in computer science (68R10) Analysis of algorithms (68W40) Approximation algorithms (68W25) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70)

Cited In (14)

• Minimum nonuniform graph partitioning with unrelated weights
• An exact algorithm for min-max hyperstructure equipartition with a connected constraint
• On a connection between small set expansions and modularity clustering
• \(\ell_p\)-norm multiway cut
• Approximation algorithms for hypergraph small set expansion and small set vertex expansion
• Hardness and efficiency on minimizing maximum distances for graphs with few \(P_4\)'s and \((k, \ell)\)-graphs
• Spanning tree congestion and computation of generalized Győri-Lovász partition
• Parameterized algorithms for min-max multiway cut and list digraph homomorphism
• Minimum spanning table and optimal expansion of competence set
• Fixed parameter approximation scheme for min-max \(k\)-cut
• Fixed parameter approximation scheme for min-max \(k\)-cut
• Approximation algorithms for hypergraph small-set expansion and small-set vertex expansion
• Polynomial-time data reduction for weighted problems beyond additive goal functions
• The small set vertex expansion problem

This page was built for publication: Min-Max Graph Partitioning and Small Set Expansion

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5494941)