Let G be a graph and \begin{document}$ (V_1,V_2,\cdots ,V_k) $\end{document} be a k-partition of G. For \begin{document}$ 1\leqslant i \lt j\leqslant k $\end{document}, the ratio of \begin{document}$ (V_i, V_j) $\end{document}, denoted by \begin{document}$ R(V_i, V_j) $\end{document}, is \begin{document}$ e(V_i, V_j)/(|V_i||V_j|) $\end{document}, where \begin{document}$ e(V_i,V_j) $\end{document} is the number of crossing edges. The minimum k-ratio of G, denoted by \begin{document}$ R_k(G) $\end{document}, is the minimum \begin{document}$ \sum _{1\leqslant i \lt j\leqslant k}R(V_i,V_j) $\end{document} over all k-partitions \begin{document}$ (V_1,V_2,\cdots ,V_k) $\end{document} of G. Let \begin{document}$ R(G)=R_2(G) $\end{document}. The ratio cut problem, posed by Wei and Cheng, and independently by Leighton and Rao, is an extension of the min-cut problem and has important applications in CAD. It is easy to see that \begin{document}$ R_k(G) $\end{document} is closely related to the density d(G) of a graph G. In this paper, we mainly give some results on \begin{document}$ R_k(G) $\end{document} with respect to d(G). First, we show that \begin{document}$ R_k(G)\leqslant {k \atopwithdelims ()2}(1+o(1))d(G) $\end{document} for graphs G and \begin{document}$ R_k(G)\leqslant (k-1)(1+o(1))d(G) $\end{document} for sparse graphs G. Then, we give some upper and lower bounds on R(G). In particular, we show \begin{document}$ R(G)\leqslant 4/(n-3) $\end{document} for every planar graph G with \begin{document}$ n\geqslant 4 $\end{document} vertices. At last, we consider the random graph G(n, p) and show that R(G(n, p)) can be determined asymptotically almost surely if \begin{document}$ p\geqslant C\log n/n $\end{document} for some constant \begin{document}$ C \gt 0 $\end{document}.
Bo Bai, Xiang Chen, Jian-Feng Hou, Gong Zhang
. On Ratio-k-Cuts of Graphs[J]. Journal of the Operations Research Society of China, 2025
, 13(2)
: 463
-483
.
DOI: 10.1007/s40305-023-00465-5
[1] Edwards, C.S.: Some extremal properties of bipartite graphs. Can. J. Math. 3, 475-485 (1973)
[2] Edwards, C.S.: An improved lower bound for the number of edges in a largest bipartite subgraph. In: Proceedings of 2nd Czechoslovak Symposium on Graph Theory, pp. 167-181 (1975)
[3] Alon, N.: Bipartite subgraphs. Combinatorica 16, 301-311 (1996)
[4] Bollobás, B., Scott, A.D.: Exact bounds for judicious partitions of graphs. Combinatorica 19, 473-486 (1999)
[5] Fan, G., Hou, J.: Bounds for pairs in judicious partitioning of graphs. Random Struct. Algorithms 50, 59-70 (2017)
[6] Fan, G., Hou, J., Yu, X.: Bisections of graphs without short cycles. Comb. Probab. Comput. 27, 44-59 (2018)
[7] Hou, J., Wu, S., Yan, G.: On judicious partitions of uniform hypergraphs. J. Comb. Theory Ser. A 141, 16-32 (2016)
[8] Hou, J., Wu, S.: Bipartitions of oriented graphs. J. Comb. Theory Ser. B 132, 107-133 (2018)
[9] Ma, J., Yu, X.: On judicious bipartitions of graphs. Combinatorica 36, 537-556 (2016)
[10] Scott, A.D.: Judicious partitions and related problems. Surv. Comb. 327, 95-117 (2005)
[11] Xu, B., Yu, X.: Triangle-free subcubic graphs with minimum bipartite density. J. Comb. Theory Ser. B 98, 516-537 (2008)
[12] Xu, B., Yu, X.: On judicious bisections of graphs. J. Comb. Theory Ser. B 106, 30-69 (2014)
[13] Zeng, Q., Hou, J.: Bipartite subgraphs of \begin{document}$ H $\end{document}-free graphs. Bull. Aust. Math. Soc. 96, 1-13 (2017)
[14] Zeng, Q., Hou, J.: Maximum cuts of graphs with forbidden cycles. ARS Mathematica Contemporanea 15, 147-160 (2018)
[15] Ford, L.R., Jr., Fulkerson, D.R.: Flows in Networks. Princeton University Press, Princeton (1962)
[16] Wei, Y.C., Cheng, C.K.: Ratio cut partitioning for hierarchical designs. IEEE Tran. Comput. Aided Design Integr. Circuits Syst. 10, 911-921 (1991)
[17] Leighton, T., Rao, S.: An approximate max-flow min-cut theorem for uniform multicommodity flow problems with applications to approximation algorithms. In: IEEE Annual Symposium on Foundations of Computer Science, pp. 422-431 (1988)
[18] Sechen, C., Chen, D.: An improved objective function for min-cut circuit partitioning. In: Proceedings of the International Conference on Computer-Aided Design, pp. 502-505 (1988)
[19] Hagen, L., Kahng, A.B.: New spectral methods for ratio cut partitioning and clustering. IEEE Trans. Comput. Aided Design Integr. Circuits Syst. 11, 1074-1085 (1992)
[20] Cheng, C.K., Hu, T.C.: Maximum concurrent flow and minimum ratio cut. Technical Report, CS pp. 88-141 (1988)
[21] Garey, M., Johnson, D.S.: Computers and Intractability: A Guide for the Theory of NP-Completeness. Freeman, San Francisco (1979)
[22] Azuma, K.: Weighted sums of certain dependent random variables. Tokuku Math. J. 19, 357-367 (1967)
[23] Hoeffding, W.: Probability inequalities for sums of bounded random variables. J. Am. Stat. Assoc. 58, 13-30 (1963)
[24] Bollobás, B., Scott, A.D.: Judicious partitions of hypergraphs. J. Comb. Theory Ser. A 78, 15-31 (1997)
[25] Ma, J., Yen, P., Yu, X.: On several partitioning problems of Bollobás and Scott. J. Comb. Theory Ser. B 100, 631-649 (2010)
[26] Spencer, J.: Ten lectures on the probabilistic method. In: SIAM Regional Conference Series in Applied Mathematics (1987)
[27] Jukna, S.: Extremal Combinatorics With Applications in Computer Science. Springer, Berlin (2011)
[28] Bien, F.: Construction of telephone networks by group representations. Not. Am. Math. Soc. 36, 5-22 (1989)
