A bisection of a graph is a bipartition of its vertex set in which the number of vertices in the two parts differ by at most 1, and its size is the number of edges which go across the two parts. Let $G$ be a graph with $n$ vertices and $m$ edges. Bollobás and Scott asked the following: What are the largest and smallest cuts that we can guarantee with bisections of $G$ ? There are reasonable sufficient conditions such that $G$ has bisections of size at least $m/2+cn$ for some $c\gt 0$ . In this paper, we study the Min-Bisection problem which has arisen in numerous contexts, and initially give some sufficient conditions such that $G$ has bisections of size at most $m/2-cn$ for some $c\gt 0$ .

Conficts of Interest

The authors declare no conflicts of interest.

Open Research

Data Availability Statement

The authors have nothing to report.

References

1J. Shi and J. Malik, “Normalized Cuts and Image Segmentation,” IEEE Transactions on Pattern Analysis and Machine Intelligence 22 (2000): 888–905.
10.1109/34.868688
Web of Science® Google Scholar
2C. J. Alpert and A. B. Kahng, “Recent Directions in Netlist Partitioning: A Survey,” Integration: VLSI Journal 19 (1995): 1–81.
10.1016/0167-9260(95)00008-4
Web of Science® Google Scholar
3 METIS. “Family of Multilevel Partitioning Algorithms,” http://www-users.cs.umn.edu/~karypis/metis/.
Google Scholar
4 JOSTLE. “Graph Partitioning Soflware,” http://stafFweb.cms.gre.ac.uk/~c.walshaw/jostle/.
Google Scholar
5T. Leighton and S. Rao, “ An Approximate Max-Flow Min-Cut Theorem for Uniform Multicommodity Flow Problems With Applications to Approximation Algorithms,” in Proceedings of the IEEE Annual Symposium on Foundions of Computer Science (1988), 422–431.
Google Scholar
6S. Arora, S. Rao, and U. Vazirani, “Expander Fows, Geometric Embeddings, and Graph Partitionings,” in 36th Annual Symposium on the Theory of Computing (2004), 222–231.
Google Scholar
7B. Bollobás and A. D. Scott, “Problems and Results on Judicious Partitions,” Random Structures & Algorithms 21 (2002): 414–430.
10.1002/rsa.10062
Web of Science® Google Scholar
8G. Fan, J. Hou, and X. Yu, “Bisections of Graphs Without Short Cycles,” Combinatorics, Probability & Computing 27 (2018): 44–59.
10.1017/S0963548317000487
Web of Science® Google Scholar
9J. Hou and J. Yan, “Max-Bisections of $H$ -Free Graphs,” Discrete Mathamatics 343, no. 1 (2020): 111590.
10.1016/j.disc.2019.07.006
Google Scholar
10J. Jin and B. Xu, “Bisections of Graphs Without ${K}_{2,l}$ ,” Discrete Applied Mathematics 259 (2019): 112–118.
10.1016/j.dam.2018.12.022
Google Scholar
11C. Lee, P. Loh, and B. Sudakov, “Bisections of Graphs,” Journal of Combinatorial Theory Series B 103 (2013): 599–629.
10.1016/j.jctb.2013.06.002
Web of Science® Google Scholar
12N. Alon, M. Krivelevich, and B. Sudakov, “Maxcut in $H$ -Free Graphs,” Combinatorics, Probability & Computing 14 (2005): 629–647.
10.1017/S0963548305007017
Google Scholar
13B. Bollobás and A. D. Scott, “Exact Bounds for Judicious Partitions of Graphs,” Combinatorica 19 (1999): 473–486.
10.1007/s004939970002
Web of Science® Google Scholar
14B. Bollobás and A. D. Scott, “Judicious Partitions of Bounded-Degree Graphs,” Journal of Graph Theory 46 (2004): 131–143.
10.1002/jgt.10174
Web of Science® Google Scholar
15Y. Ji, J. Ma, J. Yan, and X. Yu, “On Problems About Judicious Bipartitions of Graphs,” Journal of Combinatorial Theory, Series B 139 (2019): 230–250.
10.1016/j.jctb.2019.03.001
Web of Science® Google Scholar
16J. Ma and T. Yang, “Decomposing ${C}_{4}$ -Free Graphs Under Degree Constraints,” Journal of Graph Theory 90 (2019): 13–23.
10.1002/jgt.22364
Google Scholar
17J. Ma, P. Yen, and X. Yu, “On Several Partitioning Problems of Bollobás and Scott,” Journal of Combinatorial Theory Series B 100 (2010): 631–649.
10.1016/j.jctb.2010.06.002
Web of Science® Google Scholar
18J. Ma and X. Yu, “On Judicious Bipartitions of Graphs,” Combinatorica 36 (2016): 537–556.
10.1007/s00493-015-2944-y
Web of Science® Google Scholar
19B. Xu and X. Yu, “Triangle-Free Subcubic Graphs With Minimum Bipartite Density,” Journal of Combinatorial Theory, Series B 98 (2008): 516–537.
10.1016/j.jctb.2007.09.001
Web of Science® Google Scholar
20B. Xu, J. Yan, and X. Yu, “Balanced Judicious Bipartitions of Graphs,” Journal of Graph Theory 63 (2010): 210–225.
10.1002/jgt.20421
Web of Science® Google Scholar
21B. Xu, J. Yan, and X. Yu, “A Note on Balanced Bipartitions,” Discrete Math. 310 (2010): 2613–2617.
10.1016/j.disc.2010.03.029
Web of Science® Google Scholar
22B. Xu and X. Yu, “On Judicious Bisections of Graphs,” Journal of Combinatorial Theory, Series B 106 (2014): 30–69.
10.1016/j.jctb.2014.01.004
Web of Science® Google Scholar
23G. Fan, B. Xu, X. Yu, and C. Zhou, “Upper Bounds on Minimum Balanced Bipartitions,” Discrete Mathematics 312 (2012): 1077–1083.
10.1016/j.disc.2011.11.030
Web of Science® Google Scholar
24H. Li, Y. Liang, M. Liu, and B. Xu, “On Minimum Balanced Bipartitions of Triangle-Free Graphs,” Journal of Combinatorial Optimization 27 (2014): 557–566.
10.1007/s10878-012-9539-y
Web of Science® Google Scholar
25K. Azuma, “Weighted Sums of Certain Dependent Random Variables,” Tokuku Mathematics Journal 19 (1967): 357–367.
Google Scholar
26W. Hoeffding, “Probability Inequalities for Sums of Bounded Random Variables,” Journal of the American Statistical Association 58 (1963): 13–30.
10.1080/01621459.1963.10500830
Web of Science® Google Scholar
27S. Janson, T. Łuczak, and A. Ruciński, Random Graphs (Wiley, 2000).
10.1002/9781118032718
Google Scholar
28N. Alon, B. Bollobás, M. Krivelevich, and B. Sudakov, “Maximum Cuts and Judicious Partitions in Graphs Without Short Cycles,” Journal of Combinatorial Theory, Series B 88 (2003): 329–346.
10.1016/S0095-8956(03)00036-4
Web of Science® Google Scholar
29S. Jukna, Extremal Combinatorics With Applications in Computer Science (Springer, 2011).
10.1007/978-3-642-17364-6
Google Scholar
30A. Shantanam, “Minimum Balanced Bipartitions of Planar Triangulations,” Discrete Mathematics 343 (2020): 111572.
10.1016/j.disc.2019.06.028
Web of Science® Google Scholar
31W. Wang and K. Lih, “On the Sizes of Graphs Embeddable in Surfaces of Nonnegative Euler Characteristic and Their Applications to Edge Choosability,” European Journal of Combinatorics 28 (2007): 111–120.
10.1016/j.ejc.2005.09.002
Web of Science® Google Scholar
32A. Bondy and M. Simonovits, “Cycles of Even Length in Graphs,” Journal of Combinatorial Theory, Series B 16 (1974): 97–105.
10.1016/0095-8956(74)90052-5
Google Scholar

Early View

Online Version of Record before inclusion in an issue

On Min-Bisections of Graphs

ABSTRACT

Conficts of Interest

Open Research

Data Availability Statement

References

References

Information

About Wiley Online Library

Help & Support

Opportunities

Connect with Wiley

On Min-Bisections of Graphs

ABSTRACT

Conficts of Interest

Open Research

Data Availability Statement

References

References

Related

Information