Min-Max Graph Partitioning and Small Set Expansion

DOI10.1137/120873996MaRDI QIDQ5494941zbMATH OpenOpenAlexFDO

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)

Full work available at URL https://arxiv.org/abs/1110.4319, https://research.tue.nl/nl/publications/ae03f43a-d42e-4409-82a9-3990d7df3759

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)

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.

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

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
• _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
• Parameterized algorithms for min-max multiway cut and list digraph homomorphism
• Spanning tree congestion and computation of generalized Győri-Lovász partition
• 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)