Balanced Judicious Bipartition is Fixed-Parameter Tractable

DOI10.1137/17M1155612zbMATH Open1425.05129arXiv1710.05491OpenAlexW2979456162WikidataQ127126725 ScholiaQ127126725MaRDI QIDQ5238741FDOQ5238741

Authors: Daniel Lokshtanov, Saket Saurabh, Roohani Sharma, Meirav Zehavi 

Publication date: 28 October 2019

Published in: SIAM Journal on Discrete Mathematics (Search for Journal in Brave)

Abstract: The family of judicious partitioning problems, introduced by Bollob'as and Scott to the field of extremal combinatorics, has been extensively studied from a structural point of view for over two decades. This rich realm of problems aims to counterbalance the objectives of classical partitioning problems such as Min Cut, Min Bisection and Max Cut. While these classical problems focus solely on the minimization/maximization of the number of edges crossing the cut, judicious (bi)partitioning problems ask the natural question of the minimization/maximization of the number of edges lying in the (two) sides of the cut. In particular, Judicious Bipartition (JB) seeks a bipartition that is "judicious" in the sense that neither side is burdened by too many edges, and Balanced JB also requires that the sizes of the sides themselves are "balanced" in the sense that neither of them is too large. Both of these problems were defined in the work by Bollob'as and Scott, and have received notable scientific attention since then. In this paper, we shed light on the study of judicious partitioning problems from the viewpoint of algorithm design. Specifically, we prove that BJB is FPT (which also proves that JB is FPT).

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

Recommendations

• Balanced judicious bipartition is fixed-parameter tractable
• scientific article; zbMATH DE number 6311292
• Balanced judicious bipartitions of graphs
• Bounds for judicious balanced bipartitions of graphs
• Approximation algorithm for the balanced 2-connected bipartition problem
• Improved approximation algorithms for balanced partitioning problems
• Approximation and parameterized algorithms for balanced connected partition problems
• On the parameterized complexity of computing balanced partitions in graphs
• Balanced judicious partitions of \((k,k-1)\)-biregular graphs
• The balanced satisfactory partition problem

zbMATH Keywords

judicious partitiontree decompositionminimum bisectionfixed-parameter tractablerandomized contractions

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Extremal problems in graph theory (05C35) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70)

Cites Work

• Parameterizing above or below guaranteed values
• Title not available (Why is that?)
• Parameterizing above Guaranteed Values: MaxSat and MaxCut
• Parameterized graph separation problems
• Judicious partitions of hypergraphs
• Maximum cuts and judicious partitions in graphs without short cycles
• Exact bounds for judicious partitions of graphs
• Judicious partitions and related problems
• On judicious bisections of graphs
• Title not available (Why is that?)
• Problems and results on judicious partitions
• Judicious partitions of uniform hypergraphs
• Some Extremal Properties of Bipartite Subgraphs
• Judicious \(k\)-partitions of graphs
• Judicious partitions of 3-uniform hypergraphs
• Balanced judicious bipartitions of graphs
• On judicious bipartitions of graphs
• Judicious partitions of graphs
• An improved parameterized algorithm for the minimum node multiway cut problem
• Judicious partitions of bounded‐degree graphs
• Fixed-Parameter Tractability of Multicut Parameterized by the Size of the Cutset
• The minimum \(k\)-way cut of bounded size is fixed-parameter tractable
• Faster parameterized algorithms using linear programming
• Note on maximal bisection above tight lower bound
• Maximum balanced subgraph problem parameterized above lower bound
• Max \(k\)-cut and judicious \(k\)-partitions
• \textsc{Max-Cut} parameterized above the Edwards-Erdős bound
• Bisections above Tight Lower Bounds
• Minimum bisection is fixed parameter tractable
• Designing FPT algorithms for cut problems using randomized contractions
• Representative families: a unified tradeoff-based approach
• Judicious partitions of directed graphs
• Linear kernels and linear-time algorithms for finding large cuts
• Parameterized and approximation algorithms for the load coloring problem
• Parameterized algorithms for load coloring problem
• Constraint Satisfaction Problems Parameterized above or below Tight Bounds: A Survey
• Multi-parameter analysis for local graph partitioning problems: using greediness for parameterization
• \((k,n-k)\)-max-cut: an \({\mathcal O}^*(2^p)\)-time algorithm and a polynomial kernel

Cited In (4)

• Balanced judicious bipartition is fixed-parameter tractable
• Better Balance by Being Biased: A 0.8776-Approximation for Max Bisection
• Perfect forests in graphs and their extensions
• On the parameterized complexity of the Maximum Exposure Problem

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

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