Fast balanced partitioning is hard even on grids and trees

DOI10.1016/J.TCS.2013.03.014zbMATH Open1292.68165arXiv1111.6745OpenAlexW2005606079MaRDI QIDQ388790FDOQ388790

Authors: Andreas Emil Feldmann 

Publication date: 7 January 2014

Published in: Theoretical Computer Science (Search for Journal in Brave)

Abstract: Two kinds of approximation algorithms exist for the k-BALANCED PARTITIONING problem: those that are fast but compute unsatisfying approximation ratios, and those that guarantee high quality ratios but are slow. In this paper we prove that this tradeoff between runtime and solution quality is necessary. For the problem a minimum number of edges in a graph need to be found that, when cut, partition the vertices into k equal-sized sets. We develop a reduction framework which identifies some necessary conditions on the considered graph class in order to prove the hardness of the problem. We focus on two combinatorially simple but very different classes, namely trees and solid grid graphs. The latter are finite connected subgraphs of the infinite 2D grid without holes. First we use the framework to show that for solid grid graphs it is NP-hard to approximate the optimum number of cut edges within any satisfying ratio. Then we consider solutions in which the sets may deviate from being equal-sized. Our framework is used on grids and trees to prove that no fully polynomial time algorithm exists that computes solutions in which the sets are arbitrarily close to equal-sized. This is true even if the number of edges cut is allowed to increase the more stringent the limit on the set sizes is. These are the first bicriteria inapproximability results for the problem.

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

Recommendations

• Fast balanced partitioning is hard even on grids and trees
• Balanced partitions of trees and applications
• Balanced partitions of trees and applications
• Balanced graph partitioning
• Improved approximation algorithms for balanced partitioning problems

zbMATH Keywords

treesinapproximabilitygrid graphsbalanced partitioningbicriteria approximation

Mathematics Subject Classification ID

Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Approximation algorithms (68W25) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70)

Cites Work

• Title not available (Why is that?)
• Ruling Out PTAS for Graph Min‐Bisection, Dense k‐Subgraph, and Bipartite Clique
• Applications of a Planar Separator Theorem
• Balanced graph partitioning
• Title not available (Why is that?)
• Some simplified NP-complete graph problems
• Highly connected sets and the excluded grid theorem
• Multicommodity max-flow min-cut theorems and their use in designing approximation algorithms
• Title not available (Why is that?)
• Partitioning graphs into balanced components
• Expander flows, geometric embeddings and graph partitioning
• A scalable multi-level preconditioner for matrix-free µ-finite element analysis of human bone structures
• A framework for solving VLSI graph layout problems
• How Good is Recursive Bisection?
• Excluded minors, network decomposition, and multicommodity flow
• Parallel approximation schemes for problems on planar graphs
• Balanced partitions of trees and applications
• Fast balanced partitioning is hard even on grids and trees
• An \(\mathcal{O}(n^4)\) time algorithm to compute the bisection width of solid grid graphs
• Restricted cuts for bisections in solid grids: a proof via polygons
• Edge Separators of Planar and Outerplanar Graphs With Applications
• Fast Approximate Graph Partitioning Algorithms
• The bisection width of grid graphs
• Finding minimum-quotient cuts in planar graphs

Cited In (4)

• Balanced partitions of trees and applications
• On the parameterized complexity of computing balanced partitions in graphs
• Balanced connected partitioning of unweighted grid graphs
• Fast balanced partitioning is hard even on grids and trees

Uses Software

• METIS
• PT-Scotch

This page was built for publication: Fast balanced partitioning is hard even on grids and trees

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