Document Open Access Logo

Sketching Distances in Monotone Graph Classes

Authors Louis Esperet , Nathaniel Harms , Andrey Kupavskii

PDF
Thumbnail PDF

File

LIPIcs.APPROX-RANDOM.2022.18.pdf
  • Filesize: 0.85 MB
  • 23 pages

Document Identifiers

Author Details

Louis Esperet
  • Univ. Grenoble Alpes, CNRS, Laboratoire G-SCOP, Grenoble, France
Nathaniel Harms
  • University of Waterloo, Canada
Andrey Kupavskii
  • Univ. Grenoble Alpes, CNRS, Laboratoire G-SCOP, Grenoble, France
  • Moscow Institute of Physics and Technology, Russia
  • Huawei R&D Moscow, Russia

Funding

  • Esperet, Louis: supported by the French ANR Projects GATO (ANR-16-CE40-0009-01), GrR (ANR-18-CE40-0032), TWIN-WIDTH (ANR-21-CE48-0014-01), and by LabEx PERSYVAL-lab (ANR-11-LABX-0025).

Acknowledgements

We thank Gwenaël Joret for many helpful discussions. We thank Viktor Zamaraev for leading us to Corollary 3.6 and carefully proofreading our manuscript. We thank Alexandr Andoni for a helpful discussion and for sharing with us the manuscript [Andoni and Krauthgamer, 2008]. We thank Renato Ferreira Pinto Jr. and Sebastian Wild for comments on the presentation of this article.

Cite AsGet BibTex

Louis Esperet, Nathaniel Harms, and Andrey Kupavskii. Sketching Distances in Monotone Graph Classes. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 245, pp. 18:1-18:23, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)
https://doi.org/10.4230/LIPIcs.APPROX/RANDOM.2022.18

Abstract

We study the problems of adjacency sketching, small-distance sketching, and approximate distance threshold (ADT) sketching for monotone classes of graphs. The algorithmic problem is to assign random sketches to the vertices of any graph G in the class, so that adjacency, exact distance thresholds, or approximate distance thresholds of two vertices u,v can be decided (with probability at least 2/3) from the sketches of u and v, by a decoder that does not know the graph. The goal is to determine when sketches of constant size exist. Our main results are that, for monotone classes of graphs: constant-size adjacency sketches exist if and only if the class has bounded arboricity; constant-size small-distance sketches exist if and only if the class has bounded expansion; constant-size ADT sketches imply that the class has bounded expansion; any class of constant expansion (i.e. any proper minor closed class) has a constant-size ADT sketch; and a class may have arbitrarily small expansion without admitting a constant-size ADT sketch.

Subject Classification

ACM Subject Classification
  • Theory of computation → Randomness, geometry and discrete structures
  • Theory of computation → Graph algorithms analysis
  • Theory of computation → Distributed algorithms
  • Theory of computation → Sketching and sampling
Keywords
  • adjacency labelling
  • informative labelling
  • distance sketching
  • adjacency sketching
  • communication complexity

Metrics

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

Related Versions

References

  1. Ittai Abraham, Shiri Chechik, and Cyril Gavoille. Fully dynamic approximate distance oracles for planar graphs via forbidden-set distance labels. In Proceedings of the forty-fourth annual ACM Symposium on Theory of Computing (STOC 2012), pages 1199-1218, 2012. Google Scholar
  2. Ittai Abraham and Cyril Gavoille. Object location using path separators. In Proceedings of the twenty-fifth annual ACM Symposium on Principles of Distributed Computing (PODC 2006), pages 188-197, 2006. Google Scholar
  3. Ittai Abraham, Cyril Gavoille, Anupam Gupta, Ofer Neiman, and Kunal Talwar. Cops, robbers, and threatening skeletons: Padded decomposition for minor-free graphs. SIAM Journal on Computing, 48(3):1120-1145, 2019. Google Scholar
  4. Noga Alon, Yossi Matias, and Mario Szegedy. The space complexity of approximating the frequency moments. Journal of Computer and system sciences, 58(1):137-147, 1999. Google Scholar
  5. Noga Alon and Joel H Spencer. The probabilistic method. John Wiley & Sons, 2016. Google Scholar
  6. Stephen Alstrup, Philip Bille, and Theis Rauhe. Labeling schemes for small distances in trees. SIAM Journal on Discrete Mathematics, 19(2):448-462, 2005. Google Scholar
  7. Stephen Alstrup, Søren Dahlgaard, Mathias Bæk Tejs Knudsen, and Ely Porat. Sublinear distance labeling. In 24th Annual European Symposium on Algorithms (ESA 2016). Schloss Dagstuhl-Leibniz-Zentrum für Informatik, 2016. Google Scholar
  8. Stephen Alstrup, Cyril Gavoille, Esben Bistrup Halvorsen, and Holger Petersen. Simpler, faster and shorter labels for distances in graphs. In Proceedings of the twenty-seventh annual ACM-SIAM Symposium on Discrete Algorithms (SODA 2016), pages 338-350. SIAM, 2016. Google Scholar
  9. Stephen Alstrup, Inge Li Gørtz, Esben Bistrup Halvorsen, and Ely Porat. Distance labeling schemes for trees. In 43rd International Colloquium on Automata, Languages, and Programming (ICALP 2016). Schloss Dagstuhl-Leibniz-Zentrum für Informatik, 2016. Google Scholar
  10. Alexandr Andoni and Robert Krauthgamer. Distance estimation protocols for general metrics. https://www.cs.columbia.edu/~andoni/papers/de.pdf, 2008.
  11. Alexandr Andoni, Robert Krauthgamer, and Ilya P. Razenshteyn. Sketching and embedding are equivalent for norms. SIAM J. Comput., 47(3):890-916, 2018. URL: https://doi.org/10.1137/15M1017958.
  12. 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. IEEE Computer Society, 1990. URL: https://doi.org/10.1109/FSCS.1990.89571.
  13. Alexander R. Block, Simina Branzei, Hemanta K. Maji, Himanshi Mehta, Tamalika Mukherjee, and Hai H. Nguyen. P₄-free partition and cover numbers and application. Cryptology ePrint Archive, Report 2020/1605, 2020. URL: https://ia.cr/2020/1605.
  14. Édouard Bonnet, Colin Geniet, Eun Jung Kim, Stéphan Thomassé, and Rémi Watrigant. Twin-width II: small classes. In Proceedings of the 2021 ACM-SIAM Symposium on Discrete Algorithms (SODA 2021), pages 1977-1996. SIAM, 2021. Google Scholar
  15. Arkadev Chattopadhyay, Shachar Lovett, and Marc Vinyals. Equality alone does not simulate randomness. In 34th Computational Complexity Conference (CCC 2019). Schloss Dagstuhl-Leibniz-Zentrum für Informatik, 2019. Google Scholar
  16. Victor Chepoi, Arnaud Labourel, and Sébastien Ratel. On density of subgraphs of Cartesian products. Journal of Graph Theory, 93(1):64-87, 2020. Google Scholar
  17. Erik D Demaine, Felix Reidl, Peter Rossmanith, Fernando Sánchez Villaamil, Somnath Sikdar, and Blair D Sullivan. Structural sparsity of complex networks: Bounded expansion in random models and real-world graphs. arXiv preprint, 2014. URL: http://arxiv.org/abs/1406.2587.
  18. Zdeněk Dvorák. A note on sublinear separators and expansion. European J. Combin., 93:103273, 2021. URL: https://doi.org/10.1016/j.ejc.2020.103273.
  19. Zdeněk Dvorák and Sergey Norin. Strongly sublinear separators and polynomial expansion. SIAM J. Discret. Math., 30(2):1095-1101, 2016. URL: https://doi.org/10.1137/15M1017569.
  20. Talya Eden, Piotr Indyk, and Haike Xu. Embeddings and labeling schemes for A^*. In 13th Innovations in Theoretical Computer Science Conference (ITCS 2022), volume 215, page 62. Schloss Dagstuhl-Leibniz-Zentrum für Informatik, 2022. Google Scholar
  21. Louis Esperet, Nathaniel Harms, and Viktor Zamaraev. Optimal adjacency labels for subgraphs of cartesian products. arXiv preprint, 2022. URL: http://arxiv.org/abs/2206.02872.
  22. Jittat Fakcharoenphol and Kunal Talwar. An improved decomposition theorem for graphs excluding a fixed minor. In Approximation, Randomization, and Combinatorial Optimization: Algorithms and Techniques, pages 36-46. Springer, 2003. Google Scholar
  23. Arnold Filtser. Scattering and sparse partitions, and their applications. In 47th International Colloquium on Automata, Languages, and Programming (ICALP 2020). Schloss Dagstuhl-Leibniz-Zentrum für Informatik, 2020. Google Scholar
  24. Pierre Fraigniaud and Amos Korman. On randomized representations of graphs using short labels. In Proceedings of the twenty-first annual Symposium on Parallelism in Algorithms and Architectures (SPAA 2009), pages 131-137, 2009. Google Scholar
  25. Ofer Freedman, Paweł Gawrychowski, Patrick K Nicholson, and Oren Weimann. Optimal distance labeling schemes for trees. In Proceedings of the ACM Symposium on Principles of Distributed Computing (PODC 2017), pages 185-194, 2017. Google Scholar
  26. Jakub Gajarský, Stephan Kreutzer, Jaroslav Nešetřil, Patrice Ossona de Mendez, Michał Pilipczuk, Sebastian Siebertz, and Szymon Toruńczyk. First-order interpretations of bounded expansion classes. ACM Trans. Comput. Logic, 21(4), July 2020. URL: https://doi.org/10.1145/3382093.
  27. Jakub Gajarský, Michał Pilipczuk, and Szymon Toruńczyk. Stable graphs of bounded twin-width. arXiv preprint, 2021. URL: http://arxiv.org/abs/2107.03711.
  28. Cyril Gavoille, Michal Katz, Nir A Katz, Christophe Paul, and David Peleg. Approximate distance labeling schemes. In European Symposium on Algorithms (ESA 2001), pages 476-487. Springer, 2001. Google Scholar
  29. Cyril Gavoille and Arnaud Labourel. On local representation of distances in trees. In Proceedings of the twenty-sixth annual ACM Symposium on Principles of Distributed Computing (PODC 2007), pages 352-353, 2007. Google Scholar
  30. Cyril Gavoille and David Peleg. Compact and localized distributed data structures. Distributed Computing, 16(2):111-120, 2003. Google Scholar
  31. Cyril Gavoille, David Peleg, Stéphane Pérennes, and Ran Raz. Distance labeling in graphs. Journal of Algorithms, 53(1):85-112, 2004. Google Scholar
  32. Paweł Gawrychowski and Przemysław Uznański. Better distance labeling for unweighted planar graphs. In Workshop on Algorithms and Data Structures (WADS 2021), pages 428-441. Springer, 2021. Google Scholar
  33. Ron L. Graham. On primitive graphs and optimal vertex assignments. Annals of the New York academy of sciences, 175(1):170-186, 1970. Google Scholar
  34. Martin Grohe, Stephan Kreutzer, and Sebastian Siebertz. Deciding first-order properties of nowhere dense graphs. Journal of the ACM (JACM), 64(3):1-32, 2017. Google Scholar
  35. Anupam Gupta, Ilan Newman, Yuri Rabinovich, and Alistair Sinclair. Cuts, trees and 𝓁₁-embeddings of graphs. Combinatorica, 24(2):233-269, 2004. Google Scholar
  36. Lianna Hambardzumyan, Hamed Hatami, and Pooya Hatami. A counter-example to the probabilistic universal graph conjecture via randomized communication complexity, 2021. URL: http://arxiv.org/abs/2111.10436.
  37. Lianna Hambardzumyan, Hamed Hatami, and Pooya Hatami. Dimension-free bounds and structural results in communication complexity. Electronic Colloquium on Computational Complexity (ECCC), page 66, 2021. URL: https://eccc.weizmann.ac.il/report/2021/066.
  38. Nathaniel Harms. Universal communication, universal graphs, and graph labeling. In 11th Innovations in Theoretical Computer Science Conference (ITCS 2020), volume 151, page 33. Schloss Dagstuhl-Leibniz-Zentrum für Informatik, 2020. Google Scholar
  39. Nathaniel Harms. Adjacency labeling and sketching for induced subgraphs of the hypercube. https://cs.uwaterloo.ca/~nharms/downloads/hypercube_sketch.pdf, 2022.
  40. Nathaniel Harms, Sebastian Wild, and Viktor Zamaraev. Randomized communication and implicit graph representations. In Proceedings of the 54th annual ACM Symposium on Theory of Computing (STOC), 2022. Google Scholar
  41. Hamed Hatami and Pooya Hatami. The implicit graph conjecture is false. arXiv preprint arXiv:2111.13198, 2021. Google Scholar
  42. Wei Huang, Yaoyun Shi, Shengyu Zhang, and Yufan Zhu. The communication complexity of the hamming distance problem. Information Processing Letters, 99(4):149-153, 2006. Google Scholar
  43. Tony Huynh, Bojan Mohar, Robert Šámal, Carsten Thomassen, and David R Wood. Universality in minor-closed graph classes. arXiv preprint, 2021. URL: http://arxiv.org/abs/2109.00327.
  44. Piotr Indyk. Stable distributions, pseudorandom generators, embeddings, and data stream computation. Journal of the ACM (JACM), 53(3):307-323, 2006. Google Scholar
  45. Piotr Indyk and Rajeev Motwani. Approximate nearest neighbors: towards removing the curse of dimensionality. In Proceedings of the thirtieth annual ACM Symposium on Theory of Computing (STOC 1998), pages 604-613, 1998. Google Scholar
  46. T.S. Jayram. Problem 25: Communication complexity and metric spaces. https://sublinear.info/25, 2009.
  47. Sampath Kannan, Moni Naor, and Steven Rudich. Implicit representation of graphs. SIAM Journal on Discrete Mathematics, 5(4):596-603, 1992. Google Scholar
  48. Subhash Khot and Assaf Naor. The Andoni-Krauthgamer-Razenshteyn characterization of sketchable norms fails for sketchable metrics. In Proceedings of the thirtieth annual ACM-SIAM Symposium on Discrete Algorithms (SODA 2019), pages 1814-1824. SIAM, 2019. Google Scholar
  49. Philip 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 (STOC 1993), pages 682-690, 1993. Google Scholar
  50. Daniela Kühn and Deryk Osthus. Every graph of sufficiently large average degree contains a C₄-free subgraph of large average degree. Combinatorica, 24(1):155-162, 2004. Google Scholar
  51. Eyal Kushilevitz, Rafail Ostrovsky, and Yuval Rabani. Efficient search for approximate nearest neighbor in high dimensional spaces. SIAM Journal on Computing, 30(2):457-474, 2000. Google Scholar
  52. 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), pages 193-201. SIAM, 2010. Google Scholar
  53. Hong Liu and Richard Montgomery. A solution to Erdős and Hajnal’s odd cycle problem. arXiv preprint, 2020. URL: http://arxiv.org/abs/2010.15802.
  54. Jiří Matoušek. Lectures on discrete geometry, volume 212. Springer Science & Business Media, 2013. Google Scholar
  55. John H Muller. Local structure in graph classes, 1989. Google Scholar
  56. Jaroslav Nešetřil and Patrice Ossona de Mendez. Grad and classes with bounded expansion II. algorithmic aspects. European Journal of Combinatorics, 29(3):777-791, 2008. Google Scholar
  57. Jaroslav Nešetřil and Patrice Ossona de Mendez. Sparsity: graphs, structures, and algorithms, volume 28. Springer-Verlag, 2012. Google Scholar
  58. Jaroslav Nešetřil and Patrice Ossona de Mendez. On low tree-depth decompositions. Graphs and combinatorics, 31(6):1941-1963, 2015. Google Scholar
  59. Jaroslav Nešetřil, Patrice Ossona de Mendez, and Sebastian Siebertz. Structural properties of the first-order transduction quasiorder. In 30th EACSL Annual Conference on Computer Science Logic (CSL 2022). Schloss Dagstuhl-Leibniz-Zentrum für Informatik, 2022. Google Scholar
  60. David Peleg. Informative labeling schemes for graphs. Theor. Comput. Sci., 340(3):577-593, 2005. Google Scholar
  61. Ilya Razenshteyn. High-dimensional similarity search and sketching: algorithms and hardness. PhD thesis, Massachusetts Institute of Technology, 2017. Google Scholar
  62. Michael Saks and Xiaodong Sun. Space lower bounds for distance approximation in the data stream model. In Proceedings of the thirty-fourth annual ACM Symposium on Theory of Computing (STOC 2002), pages 360-369, 2002. Google Scholar
  63. Jeremy P. Spinrad. Efficient graph representations. American Mathematical Society, 2003. Google Scholar
  64. Carsten Thomassen. Girth in graphs. Journal of Combinatorial Theory, Series B, 35(2):129-141, 1983. Google Scholar
  65. Mikkel Thorup. Compact oracles for reachability and approximate distances in planar digraphs. Journal of the ACM, 51(6):993-1024, 2004. Google Scholar
  66. Jan van den Heuvel, Patrice Ossona de Mendez, Daniel Quiroz, Roman Rabinovich, and Sebastian Siebertz. On the generalised colouring numbers of graphs that exclude a fixed minor. European Journal of Combinatorics, 66:129-144, 2017. Google Scholar
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 Imprint Privacy Contact