On Ratio-k-Cuts of Graphs
Bo Bai, Xiang Chen, Jian-Feng Hou, Gong Zhang
2025, 13(2):
463-483.
doi:10.1007/s40305-023-00465-5
Asbtract
(
6 )
References |
Related Articles |
Metrics
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}.
