Document Open Access Logo

On Strong Diameter Padded Decompositions

Author Arnold Filtser

PDF
Thumbnail PDF

File

LIPIcs.APPROX-RANDOM.2019.6.pdf
  • Filesize: 0.78 MB
  • 21 pages

Document Identifiers

Author Details

Arnold Filtser
  • Ben Gurion University of the Negev, Beersheva, Israel

Funding

  • Filtser, Arnold: Supported in part by ISF grant No. (1817/17) and by BSF grant No. 2015813.

Acknowledgements

The author would like to thank Ofer Neiman for helpful discussions.

Cite As Get BibTex

Arnold Filtser. On Strong Diameter Padded Decompositions. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 145, pp. 6:1-6:21, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019) https://doi.org/10.4230/LIPIcs.APPROX-RANDOM.2019.6

Abstract

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 * 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(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(ddim)-padded decomposition, which is also tight. We use this decomposition to construct (O(ddim),O~(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.

Subject Classification

ACM Subject Classification
  • Theory of computation → Graph algorithms analysis
  • Theory of computation → Approximation algorithms analysis
  • Theory of computation → Random projections and metric embeddings
Keywords
  • Padded decomposition
  • Strong Diameter
  • Sparse Cover
  • Doubling Dimension
  • Minor free graphs
  • Unique Games
  • Spanners
  • Distance Oracles

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads
    0
    Metadata Views

Related Versions

References

  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. URL: https://doi.org/10.1137/17M1115575.
  2. Ittai Abraham, Yair Bartal, and Ofer Neiman. Advances in metric embedding theory. Advances in Mathematics, 228(6):3026-3126, 2011. URL: https://doi.org/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. URL: https://doi.org/10.1137/1.9781611975031.108.
  4. Ittai Abraham, Cyril Gavoille, Andrew V. Goldberg, and Dahlia Malkhi. Routing in Networks with Low Doubling Dimension. In 26th IEEE International Conference on Distributed Computing Systems (ICDCS 2006), 4-7 July 2006, Lisboa, Portugal, page 75, 2006. URL: https://doi.org/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. URL: https://doi.org/10.1145/2591796.2591849.
  6. Ittai Abraham, Cyril Gavoille, Dahlia Malkhi, and Udi Wieder. Strong-Diameter Decompositions of Minor Free Graphs. Theory Comput. Syst., 47(4):837-855, 2010. URL: https://doi.org/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. URL: https://doi.org/10.4230/LIPIcs.APPROX-RANDOM.2017.18.
  8. Baruch Awerbuch. Complexity of Network Synchronization. J. ACM, 32(4):804-823, 1985. URL: https://doi.org/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. URL: https://doi.org/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. URL: https://doi.org/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. URL: https://doi.org/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. URL: https://doi.org/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. URL: https://doi.org/10.1137/1.9781611975482.145.
  14. Costas Busch, Chinmoy Dutta, Jaikumar Radhakrishnan, Rajmohan Rajaraman, and Srinivasagopalan 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. URL: https://doi.org/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. URL: https://doi.org/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. URL: https://doi.org/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. URL: https://doi.org/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. URL: https://doi.org/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. URL: https://doi.org/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. URL: https://doi.org/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. URL: https://doi.org/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. URL: https://doi.org/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 Optimization: Algorithms and Techniques, 6th International Workshop on Approximation Algorithms for Combinatorial Optimization Problems, APPROX 2003 and 7th International Workshop on Randomization and Approximation Techniques in Computer Science, RANDOM 2003, Princeton, NJ, USA, August 24-26, 2003, Proceedings, pages 36-46, 2003. URL: https://doi.org/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. URL: https://doi.org/10.1137/05064299X.
  25. Arnold Filtser, Robert Krauthgamer, and Ohad Trabelsi. Relaxed Voronoi: A Simple Framework 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. URL: https://doi.org/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. URL: https://doi.org/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. URL: https://doi.org/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. URL: https://doi.org/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. URL: https://doi.org/10.1109/SFCS.2003.1238226.
  30. David S. Johnson. The NP-Completeness Column: An Ongoing Guide. J. Algorithms, 8(2):285-303, 1987. URL: https://doi.org/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. URL: https://doi.org/10.1007/s00453-016-0213-0.
  32. 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. URL: https://doi.org/10.1145/509907.510017.
  33. 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. URL: https://doi.org/10.1145/167088.167261.
  34. 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. URL: https://doi.org/10.1109/FOCS.2004.41.
  35. 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. URL: https://doi.org/10.1137/1.9781611973075.18.
  36. Nathan Linial and Michael E. Saks. Low diameter graph decompositions. Combinatorica, 13(4):441-454, 1993. URL: https://doi.org/10.1007/BF01303516.
  37. Jiri Matoušek. Lectures on discrete geometry. Springer-Verlag, New York, 2002. URL: https://doi.org/10.1007/978-1-4613-0039-7.
  38. 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. URL: https://doi.org/10.1145/2755573.2755574.
  39. 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. URL: https://doi.org/10.1145/1667053.1667060.
  40. 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. URL: https://doi.org/10.1145/780542.780609.
  41. 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. URL: https://doi.org/10.1145/304893.304983.
  42. Neil Robertson and Paul D. Seymour. Graph Minors. XVI. Excluding a non-planar graph. J. Comb. Theory, Ser. B, 89(1):43-76, 2003. URL: https://doi.org/10.1016/S0095-8956(03)00042-X.
  43. 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. URL: https://doi.org/10.1007/978-3-642-03456-5_19.
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact