Fast balanced partitioning is hard even on grids and trees

DOI10.1016/J.TCS.2013.03.014MaRDI QIDQ388790zbMATH OpenOpenAlexFDO

Authors Andreas Emil Feldmann

Publication date 7 January 2014

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

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

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)

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.

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

Cites work

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

Describes a project that uses

Uses Software

• PT-Scotch
• METIS

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)