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