Direct Product Multicommodity Max-Concurrent-Flow Min-Sparse-Cut Theorem

We extend the max-concurrent-flow min-sparse-cut theorem from product multicommodity to direct product multicommodity. We prove that \(\Theta (\log k)\) $\mathrm{\Theta }(logk)$ 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 }\) $\frac{1}{\alpha }$ -approximation algorithm for the sparsest cut problem, where \(\alpha \) $\alpha$ is the maximum weight ratio of vertices.