The all-or-nothing flow problem in directed graphs with symmetric demand pairs. (English) Zbl 1337.90018
Summary: We study the approximability of the all-or-nothing multicommodity flow problem in directed graphs with symmetric demand pairs (SymANF). The input consists of a directed graph \(G=(V,E)\) and a collection of (unordered) pairs of nodes \(\mathcal M=\{s_1t_1,s_2t_2,\dots,s_kt_k\}\). A subset \(\mathcal M'\) of the pairs is routable if there is a feasible multicommodity flow in \(G\) such that, for each pair \(s_it_i\in\mathcal M'\), the amount of flow from \(s_i\) to \(t_i\) is at least one and the amount of flow from \(t_i\) to \(s_i\) is at least one. The goal is to find a maximum cardinality subset of the given pairs that can be routed. Our main result is a poly-logarithmic approximation with constant congestion for SymANF. We obtain this result by extending the well-linked decomposition framework of C. Chekuri et al. [in: Proceedings of the 37th annual ACM symposium on theory of computing, STOC’05. Baltimore, MD, USA, May 22–24, 2005. New York, NY: Association for Computing Machinery (ACM). 183–192 (2005; Zbl 1192.90017)] to the directed graph setting with symmetric demand pairs. We point out the importance of studying routing problems in this setting and the relevance of our result to future work.
MSC:
| 90B10 | Deterministic network models in operations research |
| 05C20 | Directed graphs (digraphs), tournaments |
| 05C21 | Flows in graphs |
| 90C35 | Programming involving graphs or networks |
Citations:
Zbl 1192.90017References:
| [1] | Adler, I.: Directed tree-width examples. J Comb. Theory Ser. B 97(5), 718-725 (2007) · Zbl 1122.05039 · doi:10.1016/j.jctb.2006.12.006 |
| [2] | Andrews, M., Chuzhoy, J., Guruswami, V., Khanna, S., Talwar, K., Zhang, L.: Inapproximability of edge-disjoint paths and low congestion routing on undirected graphs. Combinatorica 30(5), 485-520 (2010) · Zbl 1240.68113 · doi:10.1007/s00493-010-2455-9 |
| [3] | Andrews, M., Chuzhoy, J., Khanna, S., Zhang, L.: Hardness of the undirected edge-disjoint paths problem with congestion. In: Proceeding of IEEE FOCS, pp. 226-241 (2005) · Zbl 0866.68072 |
| [4] | Chekuri, C., Chuzhoy, J.: Large-treewidth graph decompositions and applications. In: Proceedings of ACM STOC (2013) · Zbl 1293.05040 |
| [5] | Chekuri, C., Chuzhoy, J.: Polynomial bounds for the grid-minor theorem. In: Proceedings of ACM STOC (2014) · Zbl 1315.05131 |
| [6] | Chekuri, C., Ene, A.: Poly-logarithmic approximation for maximum node disjoint paths with constant congestion. In: Proceedings of ACM-SIAM SODA (2013) · Zbl 1421.68200 |
| [7] | Chekuri, C., Kannan, S., Raja, A., Viswanath, P.: Multicommodity flows and cuts in polymatroidal networks. In: Proceedings of ITCS, pp. 399-408 (2012) · Zbl 1347.68278 |
| [8] | Chekuri, C., Khanna, S., Shepherd, F.B.: The all-or-nothing multicommodity flow problem. SIAM J. Comput. 42(4), 1467-1493 (2013) · Zbl 1290.68054 · doi:10.1137/100796820 |
| [9] | Chekuri, C., Khanna, S., Shepherd, F.B.: Multicommodity flow, well-linked terminals, and routing problems. In: Proceedings of ACM STOC, pp. 183-192 (2005) · Zbl 1192.90017 |
| [10] | Chekuri, C., Khanna, S., Shepherd, F.B.: Well-linked terminals for node-capacitated routing problems. Manuscript (2005) · Zbl 1192.90017 |
| [11] | Chekuri, C., Khanna, S., Shepherd, F.B.: An \[O(\sqrt{n})O\](\sqrt{n}) approximation and integrality gap for disjoint paths and unsplittable flow. Theory Comput. 2(7), 137-146 (2006) · Zbl 1213.68700 · doi:10.4086/toc.2006.v002a007 |
| [12] | Chekuri, C., Mydlarz, M., Shepherd, F.B.: Multicommodity demand flow in a tree and packing integer programs. ACM Trans. Algorithms 3(3), 27 (2007) · Zbl 1192.68879 · doi:10.1145/1273340.1273343 |
| [13] | Chuzhoy, J.: Routing in undirected graphs with constant congestion. ArXiv preprint arXiv:1107.2554 (2011). Extended abstract in STOC 2012 · Zbl 1350.68207 |
| [14] | Chuzhoy, J., Guruswami, V., Khanna, S., Talwar, K.: Hardness of routing with congestion in directed graphs. In: Proceedings of ACM STOC, pp. 165-178 (2007) · Zbl 1232.68062 |
| [15] | Chuzhoy, J., Khanna, S.: Polynomial flow-cut gaps and hardness of directed cut problems. J. ACM 56(2), 6 (2009) · Zbl 1325.68096 · doi:10.1145/1502793.1502795 |
| [16] | Chuzhoy, J., Li, S.: A polylogarithimic approximation algorithm for edge-disjoint paths with congestion 2. In: Proceedings of IEEE FOCS (2012) · Zbl 1240.68113 |
| [17] | Even, S., Itai, A., Shamir, A.: On the complexity of timetable and multicommodity flow problems. SIAM J. Comput. 5(4), 691-703 (1976) · Zbl 0358.90021 · doi:10.1137/0205048 |
| [18] | Feige, U., Hajiaghayi, M.T., Lee, J.R.: Improved approximation algorithms for minimum weight vertex separators. SIAM J. Comput. 38, 629-657 (2008) · Zbl 1172.68063 · doi:10.1137/05064299X |
| [19] | Fortune, S., Hopcroft, J., Wyllie, J.: The directed subgraph homeomorphism problem. Theor. Comput. Sci. 10(2), 111-121 (1980) · Zbl 0419.05028 · doi:10.1016/0304-3975(80)90009-2 |
| [20] | Garg, N., Vazirani, V.V., Yannakakis, M.: Primal-dual approximation algorithms for integral flow and multicut in trees. Algorithmica 18(1), 3-20 (1997) · Zbl 0873.68075 · doi:10.1007/BF02523685 |
| [21] | Johnson, T., Robertson, N., Seymour, P.D., Thomas, R.: Directed tree-width. J. Comb. Theory Ser. B 82(1), 138-154 (2001) · Zbl 1027.05045 · doi:10.1006/jctb.2000.2031 |
| [22] | Karp, R.M.: Reducibility among combinatorial problems. In: Complexity of Computer Computations, pp. 85-103. Plenum press, New York (1972) · Zbl 1467.68065 |
| [23] | Kawarabayashi, K., Kreutzer, S.: An excluded grid theorem for digraphs with forbidden minors. In: Proceedings of ACM-SIAM SODA (2014) · Zbl 1315.05132 |
| [24] | Kobayashi, Y., Kawarabayashi, K-I, Kreutzer, S.: An excluded half-integral grid theorem for digraphs and the directed disjoint paths problem. In: Proceedings of ACM STOC (2014) · Zbl 1315.05132 |
| [25] | Klein, P.N., Plotkin, S.A., Rao, S.: Excluded minors, network decomposition, and multicommodity flow. In: Proceedings of ACM STOC, pp. 682-690 (1993) · Zbl 1310.90017 |
| [26] | Klein, P.N., Plotkin, S.A., Rao, S., Tardos, E.: Approximation algorithms for Steiner and directed multicuts. J. Algorithms 22(2), 241-269 (1997) · Zbl 0866.68072 · doi:10.1006/jagm.1996.0833 |
| [27] | Leighton, T., Rao, S.: Multicommodity max-flow min-cut theorems and their use in designing approximation algorithms. J. ACM 46(6), 787-832 (1999) · Zbl 1065.68666 · doi:10.1145/331524.331526 |
| [28] | Linial, N., London, E., Rabinovich, Y.: The geometry of graphs and some of its algorithmic applications. Combinatorica 15(2), 215-245 (1995) · Zbl 0827.05021 · doi:10.1007/BF01200757 |
| [29] | Reed, B.: Introducing directed tree width. Electr. Notes Discr. Math. 3, 222-229 (1999) · Zbl 1072.05579 · doi:10.1016/S1571-0653(05)80061-7 |
| [30] | Saks, Michael E., Samorodnitsky, Alex, Zosin, Leonid: A lower bound on the integrality gap for minimum multicut in directed networks. Combinatorica 24(3), 525-530 (2004) · Zbl 1058.05033 · doi:10.1007/s00493-004-0031-x |
| [31] | Srinivasan, A.: Improved approximations for edge-disjoint paths, unsplittable flow, and related routing problems. In: Proceedings of IEEE FOCS, pp. 416-425 (1997) |
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
