Judicious partitions of directed graphs

DOI10.1002/RSA.20579zbMATH Open1330.05078arXiv1305.2986OpenAlexW2071932326WikidataQ115150369 ScholiaQ115150369MaRDI QIDQ3467583FDOQ3467583

Authors: Choongbum Lee, Po-Shen Loh, Benny Sudakov 

Publication date: 3 February 2016

Published in: Random Structures \& Algorithms (Search for Journal in Brave)

Abstract: The area of judicious partitioning considers the general family of partitioning problems in which one seeks to optimize several parameters simultaneously, and these problems have been widely studied in various combinatorial contexts. In this paper, we study essentially the most fundamental judicious partitioning problem for directed graphs, which naturally extends the classical Max Cut problem to this setting: we seek bipartitions in which many edges cross in each direction. It is easy to see that a minimum outdegree condition is required in order for the problem to be nontrivial, and we prove that every directed graph with M edges and minimum outdegree at least two admits a bipartition in which at least (1/6 + o(1))M edges cross in each direction. We also prove that if the minimum outdegree is at least three, then the constant can be increased to 1/5. If the minimum outdegree tends to infinity with N, then the constant increases to 1/4. All of these constants are best-possible, and provide asymptotic answers to a question of Alex Scott.

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

Recommendations

• A bound on judicious bipartitions of directed graphs
• Judicious partitions and related problems
• On judicious bipartitions of directed graphs
• Judicious \(k\)-partitions of graphs
• Problems and results on judicious partitions

zbMATH Keywords

directed graphsjudicious partitioning

Mathematics Subject Classification ID

Directed graphs (digraphs), tournaments (05C20) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70)

Cites Work

• Gadgets, Approximation, and Linear Programming
• Some optimal inapproximability results
• Improved approximation algorithms for MAX \(k\)-cut and MAX BISECTION
• Maximum cuts and judicious partitions in graphs without short cycles
• Exact bounds for judicious partitions of graphs
• The Bollobás-Thomason conjecture for \(3\)-uniform hypergraphs
• Judicious partitions and related problems
• Bisections of graphs
• Problems and results on judicious partitions
• Some Extremal Properties of Bipartite Subgraphs
• On several partitioning problems of Bollobás and Scott
• Partitioning 3-uniform hypergraphs
• Improved approximation algorithms for maximum cut and satisfiability problems using semidefinite programming
• Judicious partitions of 3-uniform hypergraphs
• Maximizing Several Cuts Simultaneously
• Max \(k\)-cut and judicious \(k\)-partitions
• MaxCut in ${\bm H)$-Free Graphs
• The size of the largest bipartite subgraphs
• Bipartite Subgraphs of Triangle-Free Graphs

Cited In (12)

• Balanced judicious bipartition is fixed-parameter tractable
• On bisections of graphs without complete bipartite graphs
• Balanced Judicious Bipartition is Fixed-Parameter Tractable
• On bipartitions of directed graphs with small semidegree
• Graph partitioning: an updated survey
• Bipartitions of oriented graphs
• A bound on judicious bipartitions of directed graphs
• Optimal bisections of directed graphs
• On judicious bipartitions of directed graphs
• On bisections of directed graphs
• Partitioning digraphs with outdegree at least 4
• On splitting digraphs

This page was built for publication: Judicious partitions of directed graphs

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