On strong diameter padded decompositions. (English) Zbl 07650073
Achlioptas, Dimitris (ed.) et al., Approximation, randomization, and combinatorial optimization. Algorithms and techniques, 22nd international conference, APPROX 2019, and 23rd international conference, RANDOM 2019, Massachusetts Institute of Technology, Cambridge, MA, USA, September 20–22, 2019. Proceedings. Wadern: Schloss Dagstuhl – Leibniz-Zentrum für Informatik. LIPIcs – Leibniz Int. Proc. Inform. 145, Article 6, 21 p. (2019).
Summary: Given a weighted graph \(G=(V,E,w)\), a partition of \(V\) is \(\Delta\)-bounded if the diameter of each cluster is bounded by \(\Delta\). A distribution over \(\Delta\)-bounded partitions is a \(\beta\)-padded decomposition if every ball of radius \(\gamma\Delta\) is contained in a single cluster with probability at least \(e^{-\beta\cdot\gamma}\). The weak diameter of a cluster \(C\) is measured w.r.t. distances in \(G\), while the strong diameter is measured w.r.t. distances in the induced graph \(G[C]\). The decomposition is weak/strong according to the diameter guarantee.
Formerly, it was proven that \(K_r\) free graphs admit weak decompositions with padding parameter \(O(r)\), while for strong decompositions only \(O(r^2)\) padding parameter was known. Furthermore, for the case of a graph \(G\), for which the induced shortest path metric \(d_G\) has doubling dimension ddim, a weak \(O(\text{ddim})\)-padded decomposition was constructed, which is also known to be tight. For the case of strong diameter, nothing was known.
We construct strong \(O(r)\)-padded decompositions for \(K_r\) free graphs, matching the state of the art for weak decompositions. Similarly, for graphs with doubling dimension ddim we construct a strong \(O(\text{ddim})\)-padded decomposition, which is also tight. We use this decomposition to construct \((O(\text{ddim}),\) \(\widetilde{O}(\text{ddim}))\)-sparse cover scheme for such graphs. Our new decompositions and cover have implications to approximating unique games, the construction of light and sparse spanners, and for path reporting distance oracles.
For the entire collection see [Zbl 1423.68013].
Formerly, it was proven that \(K_r\) free graphs admit weak decompositions with padding parameter \(O(r)\), while for strong decompositions only \(O(r^2)\) padding parameter was known. Furthermore, for the case of a graph \(G\), for which the induced shortest path metric \(d_G\) has doubling dimension ddim, a weak \(O(\text{ddim})\)-padded decomposition was constructed, which is also known to be tight. For the case of strong diameter, nothing was known.
We construct strong \(O(r)\)-padded decompositions for \(K_r\) free graphs, matching the state of the art for weak decompositions. Similarly, for graphs with doubling dimension ddim we construct a strong \(O(\text{ddim})\)-padded decomposition, which is also tight. We use this decomposition to construct \((O(\text{ddim}),\) \(\widetilde{O}(\text{ddim}))\)-sparse cover scheme for such graphs. Our new decompositions and cover have implications to approximating unique games, the construction of light and sparse spanners, and for path reporting distance oracles.
For the entire collection see [Zbl 1423.68013].
Keywords:
padded decomposition; strong diameter; sparse cover; doubling dimension; minor free graphs; unique games; spanners; distance oraclesReferences:
| [1] | I. Abraham and O. Neiman. Using Petal-Decompositions to Build a Low Stretch Spanning Tree. SIAM Journal on Computing, 48(2):227-248, 2019. doi:10.1137/17M1115575. · Zbl 1417.68144 · doi:10.1137/17M1115575 |
| [2] | Ittai Abraham, Yair Bartal, and Ofer Neiman. Advances in metric embedding theory. Advances in Mathematics, 228(6):3026-3126, 2011. doi:10.1016/j.aim.2011.08.003. · Zbl 1250.46016 · doi:10.1016/j.aim.2011.08.003 |
| [3] | Ittai Abraham, Shiri Chechik, Michael Elkin, Arnold Filtser, and Ofer Neiman. Ramsey Spanning Trees and their Applications. In Proceedings of the Twenty-Ninth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2018, New Orleans, LA, USA, January 7-10, 2018, pages 1650-1664, 2018. doi:10.1137/1.9781611975031.108. · Zbl 1403.05028 · doi:10.1137/1.9781611975031.108 |
| [4] | Ittai Abraham, Cyril Gavoille, Andrew V. Goldberg, and Dahlia Malkhi. Routing in Net-works with Low Doubling Dimension. In 26th IEEE International Conference on Distrib-uted Computing Systems (ICDCS 2006), 4-7 July 2006, Lisboa, Portugal, page 75, 2006. doi:10.1109/ICDCS.2006.72. · doi:10.1109/ICDCS.2006.72 |
| [5] | Ittai Abraham, Cyril Gavoille, Anupam Gupta, Ofer Neiman, and Kunal Talwar. Cops, robbers, and threatening skeletons: padded decomposition for minor-free graphs. In Symposium on Theory of Computing, STOC 2014, New York, NY, USA, May 31 -June 03, 2014, pages 79-88, 2014. doi:10.1145/2591796.2591849. · Zbl 1315.05130 · doi:10.1145/2591796.2591849 |
| [6] | Ittai Abraham, Cyril Gavoille, Dahlia Malkhi, and Udi Wieder. Strong-Diameter De-compositions of Minor Free Graphs. Theory Comput. Syst., 47(4):837-855, 2010. doi: 10.1007/s00224-010-9283-6. · Zbl 1215.68166 · doi:10.1007/s00224-010-9283-6 |
| [7] | Vedat Levi Alev and Lap Chi Lau. Approximating Unique Games Using Low Diameter Graph Decomposition. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques, APPROX/RANDOM 2017, August 16-18, 2017, Berkeley, CA, USA, pages 18:1-18:15, 2017. doi:10.4230/LIPIcs.APPROX-RANDOM.2017.18. · Zbl 1467.68217 · doi:10.4230/LIPIcs.APPROX-RANDOM.2017.18 |
| [8] | Baruch Awerbuch. Complexity of Network Synchronization. J. ACM, 32(4):804-823, 1985. doi:10.1145/4221.4227. · Zbl 0628.68045 · doi:10.1145/4221.4227 |
| [9] | Baruch Awerbuch and David Peleg. Sparse Partitions (Extended Abstract). In 31st Annual Symposium on Foundations of Computer Science, St. Louis, Missouri, USA, October 22-24, 1990, Volume II, pages 503-513, 1990. doi:10.1109/FSCS.1990.89571. · doi:10.1109/FSCS.1990.89571 |
| [10] | Yair Bartal. Probabilistic Approximations of Metric Spaces and Its Algorithmic Applications. In 37th Annual Symposium on Foundations of Computer Science, FOCS ’96, Burlington, Vermont, USA, 14-16 October, 1996, pages 184-193, 1996. doi:10.1109/SFCS.1996.548477. · doi:10.1109/SFCS.1996.548477 |
| [11] | Yair Bartal, Lee-Ad Gottlieb, Tsvi Kopelowitz, Moshe Lewenstein, and Liam Roditty. Fast, precise and dynamic distance queries. In Proceedings of the Twenty-Second Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2011, San Francisco, California, USA, January 23-25, 2011, pages 840-853, 2011. doi:10.1137/1.9781611973082.66. · Zbl 1373.68188 · doi:10.1137/1.9781611973082.66 |
| [12] | Guy E. Blelloch, Anupam Gupta, Ioannis Koutis, Gary L. Miller, Richard Peng, and Kanat Tangwongsan. Nearly-Linear Work Parallel SDD Solvers, Low-Diameter Decomposition, and Low-Stretch Subgraphs. Theory Comput. Syst., 55(3):521-554, 2014. doi:10.1007/ s00224-013-9444-5. · Zbl 1314.68361 · doi:10.1007/s00224-013-9444-5 |
| [13] | Glencora Borradaile, Hung Le, and Christian Wulff-Nilsen. Greedy spanners are optimal in doubling metrics. In Proceedings of the Thirtieth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2019, San Diego, California, USA, January 6-9, 2019, pages 2371-2379, 2019. doi:10.1137/1.9781611975482.145. · Zbl 1432.68340 · doi:10.1137/1.9781611975482.145 |
| [14] | Costas Busch, Chinmoy Dutta, Jaikumar Radhakrishnan, Rajmohan Rajaraman, and Srinivas-agopalan Srivathsan. Split and Join: Strong Partitions and Universal Steiner Trees for Graphs. In 53rd Annual IEEE Symposium on Foundations of Computer Science, FOCS 2012, New Brunswick, NJ, USA, October 20-23, 2012, pages 81-90, 2012. doi:10.1109/FOCS.2012.45. · doi:10.1109/FOCS.2012.45 |
| [15] | Costas Busch, Ryan LaFortune, and Srikanta Tirthapura. Sparse Covers for Planar Graphs and Graphs that Exclude a Fixed Minor. Algorithmica, 69(3):658-684, 2014. doi:10.1007/ s00453-013-9757-4. 6:17 · Zbl 1294.05058 · doi:10.1007/s00453-013-9757-4 |
| [16] | Gruia Călinescu, Howard J. Karloff, and Yuval Rabani. Approximation Algorithms for the 0-Extension Problem. SIAM J. Comput., 34(2):358-372, 2004. doi:10.1137/ S0097539701395978. · Zbl 1087.68128 · doi:10.1137/S0097539701395978 |
| [17] | Michael Elkin, Yuval Emek, Daniel A. Spielman, and Shang-Hua Teng. Lower-Stretch Spanning Trees. SIAM J. Comput., 38(2):608-628, 2008. doi:10.1137/050641661. · Zbl 1172.68045 · doi:10.1137/050641661 |
| [18] | Michael Elkin and Ofer Neiman. Efficient Algorithms for Constructing Very Sparse Spanners and Emulators. ACM Trans. Algorithms, 15(1):4:1-4:29, November 2018. doi:10.1145/ 3274651. · Zbl 1435.68378 · doi:10.1145/3274651 |
| [19] | Michael Elkin, Ofer Neiman, and Christian Wulff-Nilsen. Space-efficient path-reporting approximate distance oracles. Theor. Comput. Sci., 651:1-10, 2016. doi:10.1016/j.tcs.2016. 07.038. · Zbl 1359.05121 · doi:10.1016/j.tcs.2016.07.038 |
| [20] | Michael Elkin and Seth Pettie. A Linear-Size Logarithmic Stretch Path-Reporting Distance Oracle for General Graphs. ACM Trans. Algorithms, 12(4):50:1-50:31, 2016. doi:10.1145/ 2888397. · Zbl 1446.68115 · doi:10.1145/2888397 |
| [21] | Matthias Englert, Anupam Gupta, Robert Krauthgamer, Harald Räcke, Inbal Talgam-Cohen, and Kunal Talwar. Vertex Sparsifiers: New Results from Old Techniques. SIAM J. Comput., 43(4):1239-1262, 2014. doi:10.1137/130908440. · Zbl 1302.90234 · doi:10.1137/130908440 |
| [22] | Jittat Fakcharoenphol, Satish Rao, and Kunal Talwar. A tight bound on approximating arbitrary metrics by tree metrics. J. Comput. Syst. Sci., 69(3):485-497, 2004. doi:10.1016/j. jcss.2004.04.011. · Zbl 1071.68082 · doi:10.1016/j.jcss.2004.04.011 |
| [23] | Jittat Fakcharoenphol and Kunal Talwar. An Improved Decomposition Theorem for Graphs Excluding a Fixed Minor. In Approximation, Randomization, and Combinatorial Optim-ization: Algorithms and Techniques, 6th International Workshop on Approximation Al-gorithms for Combinatorial Optimization Problems, APPROX 2003 and 7th International Workshop on Randomization and Approximation Techniques in Computer Science, RAN-DOM 2003, Princeton, NJ, USA, August 24-26, 2003, Proceedings, pages 36-46, 2003. doi:10.1007/978-3-540-45198-3_4. · Zbl 1279.05053 · doi:10.1007/978-3-540-45198-3_4 |
| [24] | Uriel Feige, MohammadTaghi Hajiaghayi, and James R. Lee. Improved Approximation Algorithms for Minimum Weight Vertex Separators. SIAM J. Comput., 38(2):629-657, 2008. doi:10.1137/05064299X. · Zbl 1172.68063 · doi:10.1137/05064299X |
| [25] | Arnold Filtser, Robert Krauthgamer, and Ohad Trabelsi. Relaxed Voronoi: A Simple Frame-work for Terminal-Clustering Problems. In 2nd Symposium on Simplicity in Algorithms, SOSA@SODA 2019, January 8-9, 2019 -San Diego, CA, USA, pages 10:1-10:14, 2019. doi:10.4230/OASIcs.SOSA.2019.10. · Zbl 07902013 · doi:10.4230/OASIcs.SOSA.2019.10 |
| [26] | Arnold Filtser and Ofer Neiman. Light Spanners for High Dimensional Norms via Stochastic Decompositions. In 26th Annual European Symposium on Algorithms, ESA 2018, August 20-22, 2018, Helsinki, Finland, pages 29:1-29:15, 2018. doi:10.4230/LIPIcs.ESA.2018.29. · Zbl 1524.68407 · doi:10.4230/LIPIcs.ESA.2018.29 |
| [27] | Arnold Filtser and Shay Solomon. The Greedy Spanner is Existentially Optimal. In Proceedings of the 2016 ACM Symposium on Principles of Distributed Computing, PODC 2016, Chicago, IL, USA, July 25-28, 2016, pages 9-17, 2016. doi:10.1145/2933057.2933114. · Zbl 1376.68108 · doi:10.1145/2933057.2933114 |
| [28] | Lee-Ad Gottlieb. A Light Metric Spanner. In IEEE 56th Annual Symposium on Foundations of Computer Science, FOCS 2015, Berkeley, CA, USA, 17-20 October, 2015, pages 759-772, 2015. doi:10.1109/FOCS.2015.52. · doi:10.1109/FOCS.2015.52 |
| [29] | Anupam Gupta, Robert Krauthgamer, and James R. Lee. Bounded Geometries, Fractals, and Low-Distortion Embeddings. In 44th Symposium on Foundations of Computer Science (FOCS 2003), 11-14 October 2003, Cambridge, MA, USA, Proceedings, pages 534-543, 2003. doi:10.1109/SFCS.2003.1238226. · doi:10.1109/SFCS.2003.1238226 |
| [30] | David S. Johnson. The NP-Completeness Column: An Ongoing Guide. J. Algorithms, 8(2):285-303, 1987. doi:10.1016/0196-6774(87)90043-5. · Zbl 0626.68039 · doi:10.1016/0196-6774(87)90043-5 |
| [31] | Lior Kamma and Robert Krauthgamer. Metric Decompositions of Path-Separable Graphs. Algorithmica, 79(3):645-653, 2017. doi:10.1007/s00453-016-0213-0. · Zbl 1380.68437 · doi:10.1007/s00453-016-0213-0 |
| [32] | APPROX/RANDOM 2019 6:18 |
| [33] | On Strong Diameter Padded Decompositions · Zbl 07650073 |
| [34] | Subhash Khot. On the power of unique 2-prover 1-round games. In Proceedings on 34th Annual ACM Symposium on Theory of Computing, May 19-21, 2002, Montréal, Québec, Canada, pages 767-775, 2002. doi:10.1145/509907.510017. · Zbl 1192.68367 · doi:10.1145/509907.510017 |
| [35] | Philip N. Klein, Serge A. Plotkin, and Satish Rao. Excluded minors, network decomposition, and multicommodity flow. In Proceedings of the Twenty-Fifth Annual ACM Symposium on Theory of Computing, May 16-18, 1993, San Diego, CA, USA, pages 682-690, 1993. doi:10.1145/167088.167261. · Zbl 1310.90017 · doi:10.1145/167088.167261 |
| [36] | Robert Krauthgamer, James R. Lee, Manor Mendel, and Assaf Naor. Measured Descent: A New Embedding Method for Finite Metrics. In 45th Symposium on Foundations of Computer Science (FOCS 2004), 17-19 October 2004, Rome, Italy, Proceedings, pages 434-443, 2004. doi:10.1109/FOCS.2004.41. · doi:10.1109/FOCS.2004.41 |
| [37] | James R. Lee and Anastasios Sidiropoulos. Genus and the Geometry of the Cut Graph. In Proceedings of the Twenty-First Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2010, Austin, Texas, USA, January 17-19, 2010, pages 193-201, 2010. doi:10.1137/1. 9781611973075.18. · Zbl 1288.05062 · doi:10.1137/1.9781611973075.18 |
| [38] | Nathan Linial and Michael E. Saks. Low diameter graph decompositions. Combinatorica, 13(4):441-454, 1993. doi:10.1007/BF01303516. · Zbl 0790.05067 · doi:10.1007/BF01303516 |
| [39] | Jiri Matoušek. Lectures on discrete geometry. Springer-Verlag, New York, 2002. doi: 10.1007/978-1-4613-0039-7. · Zbl 0999.52006 · doi:10.1007/978-1-4613-0039-7 |
| [40] | Gary L. Miller, Richard Peng, Adrian Vladu, and Shen Chen Xu. Improved Parallel Algorithms for Spanners and Hopsets. In Proceedings of the 27th ACM on Symposium on Parallelism in Algorithms and Architectures, SPAA 2015, Portland, OR, USA, June 13-15, 2015, pages 192-201, 2015. doi:10.1145/2755573.2755574. · doi:10.1145/2755573.2755574 |
| [41] | Robin A. Moser and Gábor Tardos. A constructive proof of the general lovász local lemma. J. ACM, 57(2):11:1-11:15, 2010. doi:10.1145/1667053.1667060. · Zbl 1300.60024 · doi:10.1145/1667053.1667060 |
| [42] | Yuri Rabinovich. On average distortion of embedding metrics into the line and into L1. In Proceedings of the 35th Annual ACM Symposium on Theory of Computing, June 9-11, 2003, San Diego, CA, USA, pages 456-462, 2003. doi:10.1145/780542.780609. · Zbl 1192.90237 · doi:10.1145/780542.780609 |
| [43] | Satish Rao. Small distortion and volume preserving embeddings for planar and Euclidean metrics. In Proceedings of the fifteenth annual symposium on Computational geometry, SCG ’99, pages 300-306, New York, NY, USA, 1999. ACM. doi:10.1145/304893.304983. · doi:10.1145/304893.304983 |
| [44] | Neil Robertson and Paul D. Seymour. Graph Minors. XVI. Excluding a non-planar graph. J. Comb. Theory, Ser. B, 89(1):43-76, 2003. doi:10.1016/S0095-8956(03)00042-X. · Zbl 1023.05040 · doi:10.1016/S0095-8956(03)00042-X |
| [45] | Michiel H. M. Smid. The Weak Gap Property in Metric Spaces of Bounded Doubling Dimension. In Efficient Algorithms, Essays Dedicated to Kurt Mehlhorn on the Occasion of His 60th Birthday, pages 275-289, 2009. doi:10.1007/978-3-642-03456-5_19. · Zbl 1257.05053 · doi:10.1007/978-3-642-03456-5_19 |
| [46] | A Path Reporting Distance Oracles Given a weighted graph G = (V, E, w), a distance oracle is a data structure that supports distance queries between pairs u, v ∈ V . The distance oracle has stretch t, if for every query {u, v}, the estimated distance est(u, v) is within d G (u, v) and t • d G (u, v). The studied objects are stretch, size the query time. An additional requirement that been recently studied [20] is path reporting: in addition to distance estimation, the distance oracle should also return a path of the promised length. In this case, we say that distance oracle has query time q, if answering a query when the reported path has m edges, takes q + O(m) time. Path reporting distance oracles were studied for general graphs [20, 19]. For the special case of graphs excluding K r as a minor, Elkin, Neiman and Wulff-Nilsen [19] constructed a path reporting distance oracles with stretch O(r 2 ), space O(n • log Λ • log n) and query time O(log log Λ), where Λ = maxu,v d G (u,v) minu,v d G (u,v) is the aspect ratio. For this construction they used the strongly padded decomposition of [5] (in fact strong-diameter sparse covers). Implicitly, given |
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.
