Minimum bisection is fixed parameter tractable

DOI10.1145/2591796.2591852MaRDI QIDQ5259566zbMATH OpenOpenAlexFDO

Authors Marek Cygan, Daniel Lokshtanov, Marcin Pilipczuk, Michał Pilipczuk, Saket Saurabh

Publication date 26 June 2015

Published in Proceedings of the forty-sixth annual ACM symposium on Theory of computing (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1311.2563, http://wrap.warwick.ac.uk/66072/1/WRAP_1371795-cs-270115-bisection.pdf

zbMATH Keywords

fixed-parameter tractabilitytree decompositionminimum bisectionrandomized contractions

Mathematics Subject Classification ID

Graph algorithms (graph-theoretic aspects) (05C85) Analysis of algorithms and problem complexity (68Q25) Signed and weighted graphs (05C22) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70)

Abstract: In the classic Minimum Bisection problem we are given as input a graph $G$ and an integer $k$. The task is to determine whether there is a partition of $V(G)$ into two parts $A$ and $B$ such that $||A|-|B||leq1$ and there are at most $k$ edges with one endpoint in $A$ and the other in $B$. In this paper we give an algorithm for Minimum Bisection with running time $O(2^{O(k^3)}{n}^{3}lo{g}^{3}n)$. This is the first fixed parameter tractable algorithm for Minimum Bisection. At the core of our algorithm lies a new decomposition theorem that states that every graph $G$ can be decomposed by small separators into parts where each part is "highly connected" in the following sense: any cut of bounded size can separate only a limited number of vertices from each part of the decomposition. Our techniques generalize to the weighted setting, where we seek for a bisection of minimum weight among solutions that contain at most $k$ edges.

Recommendations

• Minimum bisection is fixed-parameter tractable
• On the parameterized complexity of computing graph bisections
• On minimum bisection and related partition problems in graphs with bounded tree width
• Bisections above Tight Lower Bounds
• A (probably) optimal algorithm for \textsc{bisection} on bounded-treewidth graphs

Cites work

• scientific article; zbMATH DE number 5485440 (Why is no real title available?)
• scientific article; zbMATH DE number 5485574 (Why is no real title available?)
• Advances in Cryptology – CRYPTO 2004
• Answering \(n^{2+o(1)}\) counting queries with differential privacy is hard
• Bounds on the sample complexity for private learning and private data release
• Characterizing the sample complexity of private learners
• Collusion-secure fingerprinting for digital data
• Differential privacy and the fat-shattering dimension of linear queries
• Efficient algorithms for privately releasing marginals via convex relaxations
• Faster algorithms for privately releasing marginals
• Faster private release of marginals on small databases
• Interactive privacy via the median mechanism
• Iterative Constructions and Private Data Release
• Lower bounds in differential privacy
• New Efficient Attacks on Statistical Disclosure Control Mechanisms
• On the complexity of differentially private data release, efficient algorithms and hardness results
• On the geometry of differential privacy
• Our Data, Ourselves: Privacy Via Distributed Noise Generation
• Private Learning and Sanitization: Pure vs. Approximate Differential Privacy
• The price of privately releasing contingency tables and the spectra of random matrices with correlated rows
• Theory of Cryptography

Cited in

(34)

• A polylogarithmic approximation of the minimum bisection
• Balanced judicious bipartition is fixed-parameter tractable
• On the parameterized complexity of computing graph bisections
• Exact combinatorial branch-and-bound for graph bisection
• Designing FPT algorithms for cut problems using randomized contractions
• On the complexity of computing the \(k\)-restricted edge-connectivity of a graph
• scientific article; zbMATH DE number 7525479 (Why is no real title available?)
• On the Parameterized Complexity of Counting Small-Sized Minimum \(\boldsymbol{(S,T)}\)-Cuts
• An exact combinatorial algorithm for minimum graph bisection
• Balanced Judicious Bipartition is Fixed-Parameter Tractable
• On minimum bisection and related cut problems in trees and tree-like graphs
• Multi-parameter analysis for local graph partitioning problems: using greediness for parameterization
• New abilities and limitations of spectral graph bisection
• Contraction decomposition in unit disk graphs and algorithmic applications in parameterized complexity
• A sub-exponential FPT algorithm and a polynomial kernel for minimum directed bisection on semicomplete digraphs
• Euler digraphs
• A sub-exponential FPT algorithm and a polynomial kernel for minimum directed bisection on semicomplete digraphs
• A (probably) optimal algorithm for \textsc{bisection} on bounded-treewidth graphs
• Linear kernels for separating a graph into components of bounded size
• An \(O(n^4)\) time algorithm to compute the bisection width of solid grid graphs
• On minimum bisection and related partition problems in graphs with bounded tree width
• Turing kernelization for finding long paths in graph classes excluding a topological minor
• Minimum bisection is NP-hard on unit disk graphs
• Bisection of bounded treewidth graphs by convolutions
• Parameterized algorithms for min-max multiway cut and list digraph homomorphism
• On the parameterized complexity of computing balanced partitions in graphs
• Turing kernelization for finding long paths in graphs excluding a topological minor
• Brief announcement: Bounded-degree cut is fixed-parameter tractable
• On the complexity of computing the \(k\)-restricted edge-connectivity of a graph
• A multivariate approach for weighted FPT algorithms
• Minimum Bisection Is Fixed-Parameter Tractable
• Parameterized complexity of multi-node hubs
• A multivariate framework for weighted FPT algorithms
• Fixed-Parameter Tractable Canonization and Isomorphism Test for Graphs of Bounded Treewidth

Describes a project that uses

Uses Software

• SuLQ

This page was built for publication: Minimum bisection is fixed parameter tractable

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