We extend the max-concurrent-flow min-sparse-cut theorem from product multicommodity to direct product multicommodity. We prove that $\Theta(\log k)$ is the tight gap between the max-concurrent-flow and the min-sparse-cut for direct product multicommodity, where $k$ is the number of commodities. Besides, when the network we consider is centralized, we prove that there is a $\frac{1}{\alpha}$-approximation algorithm for the sparsest cut problem, where $\alpha$ is the maximum weight ratio of vertices.
Rui Guan, Dong-Yue Liang, Wei Wang, Wei-Hua Yang
. Direct Product Multicommodity Max-Concurrent-Flow Min-Sparse-Cut Theorem[J]. Journal of the Operations Research Society of China, 2026
, 14(2)
: 719
-729
.
DOI: 10.1007/s40305-024-00567-8
[1] Arora, S., Lee, J.R., Naor, A.: Euclidean distortion and the sparsest cut. In: The Proceedings of the Thirty-seventh Annual ACM Symposium on Theory of Computing, pp. 553-562(2005)
[2] Aumann, Y., Rabani, Y.: An O(log k) approximate min-cut max-flow theorem and approximation algorithm. SIAM J. Comput. 27, 291–301(1998)
[3] Baïou, M., Barahona, F.: Sparsest cut in planar graphs, maximum concurrent flows and their connections with the max-cut problem. Math. Program. 172, 59–75(2018)
[4] Bhatt, S.N., Leighton, F.T.: A framework for solving VLSI graph layout problems. J. Comput. Syst. Sci. 28, 300–343(1984)
[5] Chawla, S., Gupta, A., Räcke, H.: Embeddings of negative-type metrics and an improved approximation to generalized sparsest cut. ACM Trans. Algorithms 4, 1–18(2008)
[6] Chawla, S., Krauthgamer, R., Kumar, R., Rabani, Y., Sivakumar, D.: On the hardness of approximating multicut and sparsest-cut. Comput. Complex. 15, 94–114(2006)
[7] Chekuri, C., Shepherd, F.B., Weibel, C.: Flow-cut gaps for integer and fractional multiflows. J. Comb. Theory Ser. B 103, 248–273(2013)
[8] Garg, N., Könemann, J.: Faster and simpler algorithms for multicommodity flow and other fractional packing problems. SIAM J. Comput. 37, 630–652(2007)
[9] Garg, N., Kumar, N., Sebö, A.: Integer plane multiflow maximisation: one-quarter-approximation and gaps. Math. Program. 175, 1–17(2021)
[10] Gupta, A., Talwar, K., Witmer, D.: Sparsest cut on bounded treewidth graphs: algorithms and hardness results. In: The Proceedings of the Forty-fifth Annual ACM Symposium on Theory of Computing, pp. 281-290(2013)
[11] Khot, S.A., Vishnoi, N.K.: The unique games conjecture, integrality gap for cut problems and embeddability of negative-type metrics into L1. J. ACM 62, 1–39(2015)
[12] Klein, P., Rao, S., Agrawal, A., Ravi, R.: An approximate max-flow min-cut relation for undirected multicommodity flow, with applications. Combinatorica 15, 187–202(1995)
[13] Krauthgamer, R., Lee, J.R., Rika, H.: Flow-cut gaps and face covers in planar graphs. In: The Proceedings of the Thirtieth Annual ACM-SIAM Symposium on Discrete Algorithms, pp. 525-534(2019)
[14] Leighton, T., Rao, S.: Multicommodity max-flow min-cut theorems and their use in designing approximation algorithms. J. ACM 46, 787–832(1999)
[15] Madan, R., Shah, D., Leveque, O.: Product multicommodity flow in wireless networks. IEEE Trans. Inf. Theory 54, 1460–1476(2008)
[16] Matula, D.W., Shahrokhi, F.: Sparsest cuts and bottlenecks in graphs. Discret. Appl.Math. 27, 113–123(1990)
[17] Plotkin, S.A., Tardos, É.: Improved bounds on the max-flow min-cut ratio for multicommodity flows. Combinatorica 15, 425–434(1995)
[18] Salmasi, A., Sidiropoulos, A., Sridhar, V.: On constant multi-commodity flow-cut gaps for families of directed minor-free graphs. In: The Proceedings of the Thirtieth Annual ACM-SIAM Symposium on Discrete Algorithms, pp. 535-553(2019)
