Balanced Judicious Bipartition is Fixed-Parameter Tractable

DOI10.4230/LIPIcs.FSTTCS.2017.40zbMath1491.05148OpenAlexW2792420076MaRDI QIDQ5136332

Roohani Sharma, Meirav Zehavi, Saket Saurabh, Daniel Lokshtanov

Publication date: 25 November 2020

Full work available at URL: http://dblp.uni-trier.de/db/conf/fsttcs/fsttcs2017.html#LokshtanovSSZ17

zbMATH Keywords

tree decompositionparameterized complexityjudicious partitionminimum bisectionodd cycle transversal

Mathematics Subject Classification ID

Extremal problems in graph theory (05C35) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Parameterized complexity, tractability and kernelization (68Q27)

Related Items (4)

Unnamed Item ⋮ Parameterized Complexity of Multi-Node Hubs ⋮ An improved kernel for max-bisection above tight lower bound ⋮ Parameterized complexity of multi-node hubs

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• On judicious bisections of graphs
• Judicious partitions of uniform hypergraphs
• \textsc{Max-Cut} parameterized above the Edwards-Erdős bound
• Parameterized graph separation problems
• Representative families: a unified tradeoff-based approach
• Max \(k\)-cut and judicious \(k\)-partitions
• Judicious \(k\)-partitions of graphs
• Parameterizing above or below guaranteed values
• Judicious partitions of graphs
• Judicious partitions of hypergraphs
• Maximum cuts and judicious partitions in graphs without short cycles
• Note on maximal bisection above tight lower bound
• Judicious partitions of 3-uniform hypergraphs
• Exact bounds for judicious partitions of graphs
• Multi-parameter analysis for local graph partitioning problems: using greediness for parameterization
• An improved parameterized algorithm for the minimum node multiway cut problem
• Parameterized algorithms for load coloring problem
• $$(k,n-k)$$ ( k , n - k ) -Max-Cut: An $${\mathcal O}^*(2^p)$$ O ∗ ( 2 p ) -Time Algorithm and a Polynomial Kernel
• Constraint Satisfaction Problems Parameterized above or below Tight Bounds: A Survey
• Designing FPT Algorithms for Cut Problems Using Randomized Contractions
• Judicious partitions of directed graphs
• Parameterizing above Guaranteed Values: MaxSat and MaxCut
• Judicious partitions of bounded‐degree graphs
• Linear Kernels and Linear-Time Algorithms for Finding Large Cuts
• Problems and results on judicious partitions
• Maximum Balanced Subgraph Problem Parameterized above Lower Bound
• Faster Parameterized Algorithms Using Linear Programming
• Balanced judicious bipartitions of graphs
• Bisections above Tight Lower Bounds
• Minimum bisection 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
• Some Extremal Properties of Bipartite Subgraphs
• On judicious bipartitions of graphs

This page was built for publication: Balanced Judicious Bipartition is Fixed-Parameter Tractable