Minimum bisection is fixed parameter tractable

DOI10.1145/2591796.2591852zbMath1315.05134arXiv1311.2563OpenAlexW2157346440MaRDI QIDQ5259566

Marek Cygan, Michał Pilipczuk, Daniel Lokshtanov, Marcin 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

zbMATH Keywords

tree decompositionfixed-parameter tractabilityminimum bisectionrandomized contractions

Mathematics Subject Classification ID

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

Related Items (27)

Linear kernels for separating a graph into components of bounded size ⋮ A Multivariate Approach for Weighted FPT Algorithms ⋮ Designing FPT Algorithms for Cut Problems Using Randomized Contractions ⋮ Parameterized algorithms for min-max multiway cut and list digraph homomorphism ⋮ A multivariate framework for weighted FPT algorithms ⋮ Bisection of bounded treewidth graphs by convolutions ⋮ Minimum bisection is NP-hard on unit disk graphs ⋮ Parameterized algorithms for graph partitioning problems ⋮ On the Parameterized Complexity of Counting Small-Sized Minimum \(\boldsymbol{(S,T)}\)-Cuts ⋮ Unnamed Item ⋮ Fixed-Parameter Tractable Canonization and Isomorphism Test for Graphs of Bounded Treewidth ⋮ Balanced Judicious Bipartition is Fixed-Parameter Tractable ⋮ Minimum Bisection Is Fixed-Parameter Tractable ⋮ On the parameterized complexity of computing balanced partitions in graphs ⋮ On the complexity of computing the \(k\)-restricted edge-connectivity of a graph ⋮ An \(O(n^4)\) time algorithm to compute the bisection width of solid grid graphs ⋮ Unnamed Item ⋮ Turing kernelization for finding long paths in graph classes excluding a topological minor ⋮ Unnamed Item ⋮ Unnamed Item ⋮ An exact combinatorial algorithm for minimum graph bisection ⋮ On the Complexity of Computing the k-restricted Edge-connectivity of a Graph ⋮ Balanced Judicious Bipartition is Fixed-Parameter Tractable ⋮ Turing Kernelization for Finding Long Paths in Graph Classes Excluding a Topological Minor ⋮ Parameterized complexity of multi-node hubs ⋮ Euler Digraphs ⋮ Multi-parameter analysis for local graph partitioning problems: using greediness for parameterization

Uses Software

• SuLQ

Cites Work

• Unnamed Item
• Unnamed Item
• Efficient algorithms for privately releasing marginals via convex relaxations
• The Geometry of Differential Privacy: The Small Database and Approximate Cases
• Faster Algorithms for Privately Releasing Marginals
• Private Learning and Sanitization: Pure vs. Approximate Differential Privacy
• Privately Releasing Conjunctions and the Statistical Query Barrier
• On the geometry of differential privacy
• Interactive privacy via the median mechanism
• The price of privately releasing contingency tables and the spectra of random matrices with correlated rows
• Lower Bounds in Differential Privacy
• Iterative Constructions and Private Data Release
• Characterizing the sample complexity of private learners
• Faster private release of marginals on small databases
• Bounds on the Sample Complexity for Private Learning and Private Data Release
• Differential Privacy and the Fat-Shattering Dimension of Linear Queries
• Our Data, Ourselves: Privacy Via Distributed Noise Generation
• New Efficient Attacks on Statistical Disclosure Control Mechanisms
• Collusion-secure fingerprinting for digital data
• On the complexity of differentially private data release
• Advances in Cryptology – CRYPTO 2004
• Answering n _{2+o(1)} counting queries with differential privacy is hard
• Theory of Cryptography

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