Minimum Bisection Is Fixed-Parameter Tractable

DOI10.1137/140988553zbMath1421.68069OpenAlexW2937927637MaRDI QIDQ4634024

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

Publication date: 7 May 2019

Published in: SIAM Journal on Computing (Search for Journal in Brave)

Full work available at URL: http://wrap.warwick.ac.uk/66072/1/WRAP_1371795-cs-270115-bisection.pdf

zbMATH Keywords

graph decompositionfixed-parameter tractabilityminimum bisection

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Nonnumerical algorithms (68W05) Graph theory (including graph drawing) in computer science (68R10)

Related Items (4)

Finding connected secluded subgraphs ⋮ First-order Logic with Connectivity Operators ⋮ A survey of parameterized algorithms and the complexity of edge modification ⋮ A sub-exponential FPT algorithm and a polynomial kernel for minimum directed bisection on semicomplete digraphs

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Connectivity and tree structure in finite graphs
• On the parameterized complexity of computing balanced partitions in graphs
• Parameterized graph separation problems
• A Menger-like property of tree-width: The finite case
• A linear-time algorithm for finding a sparse \(k\)-connected spanning subgraph of a \(k\)-connected graph
• Graph minors. XIII: The disjoint paths problem
• An improved parameterized algorithm for the minimum node multiway cut problem
• A Polylogarithmic Approximation of the Minimum Bisection
• On the Parameterized Complexity of Computing Graph Bisections
• Finding small balanced separators
• Finding small separators in linear time via treewidth reduction
• Designing FPT Algorithms for Cut Problems Using Randomized Contractions
• Approximating the minimum bisection size (extended abstract)
• Partitioning Planar Graphs
• Color-coding
• Structure Theorem and Isomorphism Test for Graphs with Excluded Topological Subgraphs
• Minimum bisection is fixed parameter tractable
• Finding topological subgraphs is fixed-parameter tractable
• Fixed-Parameter Tractability of Multicut Parameterized by the Size of the Cutset
• The Minimum k-way Cut of Bounded Size is Fixed-Parameter Tractable
• The Unique Games Conjecture, Integrality Gap for Cut Problems and Embeddability of Negative-Type Metrics into ℓ ₁
• Polynomial Time Approximation Schemes for MAX-BISECTION on Planar and Geometric Graphs

This page was built for publication: Minimum Bisection Is Fixed-Parameter Tractable