Document Open Access Logo

Approximating the Minimum Logarithmic Arrangement Problem

Authors Julián Mestre , Sergey Pupyrev

PDF
Thumbnail PDF

File

LIPIcs.ISAAC.2022.7.pdf
  • Filesize: 0.77 MB
  • 15 pages

Document Identifiers

Author Details

Julián Mestre
  • Meta Platforms Inc., USA
  • School of Computer Science, The University of Sydney, Australia
Sergey Pupyrev
  • Meta Platforms Inc., USA

Acknowledgements

We thank Okke Schrijvers, Karthik Abinav Sankararaman and Riccardo Colini Baldeschi for fruitful discussions of the problem.

Cite As Get BibTex

Julián Mestre and Sergey Pupyrev. Approximating the Minimum Logarithmic Arrangement Problem. In 33rd International Symposium on Algorithms and Computation (ISAAC 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 248, pp. 7:1-7:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022) https://doi.org/10.4230/LIPIcs.ISAAC.2022.7

Abstract

We study a graph reordering problem motivated by compressing massive graphs such as social networks and inverted indexes. Given a graph, G = (V, E), the Minimum Logarithmic Arrangement problem is to find a permutation, π, of the vertices that minimizes ∑_{(u, v) ∈ E} (1 + ⌊ lg |π(u) - π(v)| ⌋).
This objective has been shown to be a good measure of how many bits are needed to encode the graph if the adjacency list of each vertex is encoded using relative positions of two consecutive neighbors under the π order in the list rather than using absolute indices or node identifiers, which requires at least lg n bits per edge.
We show the first non-trivial approximation factor for this problem by giving a polynomial time 𝒪(log k)-approximation algorithm for graphs with treewidth k.

Subject Classification

ACM Subject Classification
  • Theory of computation → Approximation algorithms analysis
Keywords
  • approximation algorithms
  • graph compression

Metrics

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

References

  1. D Adolphson and T Ch Hu. Optimal linear ordering. SIAM Journal on Applied Mathematics, 25(3):403-423, 1973. URL: https://doi.org/10.1137/0125042.
  2. Maciej Besta and Torsten Hoefler. Survey and taxonomy of lossless graph compression and space-efficient graph representations. CoRR, abs/1806.01799, 2018. Google Scholar
  3. Avrim Blum, Prasad Chalasani, Don Coppersmith, William R. Pulleyblank, Prabhakar Raghavan, and Madhu Sudan. The minimum latency problem. In Proc. of the 26th Annual ACM Symposium on Theory of Computing, pages 163-171, 1994. URL: https://doi.org/10.1145/195058.195125.
  4. Thang Nguyen Bui and Curt Jones. Finding good approximate vertex and edge partitions is np-hard. Inf. Process. Lett., 42(3):153-159, 1992. URL: https://doi.org/10.1016/0020-0190(92)90140-Q.
  5. Moses Charikar, Mohammad Taghi Hajiaghayi, Howard Karloff, and Satish Rao. L²₂ spreading metrics for vertex ordering problems. Algorithmica, 56(4):577-604, 2010. URL: https://doi.org/10.1007/s00453-008-9191-1.
  6. Flavio Chierichetti, Ravi Kumar, Silvio Lattanzi, Michael Mitzenmacher, Alessandro Panconesi, and Prabhakar Raghavan. On compressing social networks. In Knowledge Discovery and Data Mining, pages 219-228, 2009. URL: https://doi.org/10.1145/1557019.1557049.
  7. Fan-Rong King Chung. A conjectured minimum valuation tree. SIAM Review, 20(3):601-604, 1978. URL: https://doi.org/10.1137/1020084.
  8. Fan-Rong King Chung. On optimal linear arrangements of trees. Computers & mathematics with applications, 10(1):43-60, 1984. URL: https://doi.org/10.1016/0898-1221(84)90085-3.
  9. Johanne Cohen, Fedor Fomin, Pinar Heggernes, Dieter Kratsch, and Gregory Kucherov. Optimal linear arrangement of interval graphs. In International Symposium on Mathematical Foundations of Computer Science, pages 267-279. Springer, 2006. URL: https://doi.org/10.1007/11821069_24.
  10. Nikhil R Devanur, Subhash A Khot, Rishi Saket, and Nisheeth K Vishnoi. Integrality gaps for sparsest cut and minimum linear arrangement problems. In Symposium on Theory of Computing, pages 537-546, 2006. URL: https://doi.org/10.1145/1132516.1132594.
  11. Laxman Dhulipala, Igor Kabiljo, Brian Karrer, Giuseppe Ottaviano, Sergey Pupyrev, and Alon Shalita. Compressing graphs and indexes with recursive graph bisection. In Proc. of the 22nd ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, pages 1535-1544, 2016. URL: https://doi.org/10.1145/2939672.2939862.
  12. Josep Díaz, Jordi Petit, and Maria Serna. A survey of graph layout problems. ACM Computing Surveys, 34(3):313-356, 2002. URL: https://doi.org/10.1145/568522.568523.
  13. Markus Sortland Dregi and Daniel Lokshtanov. Parameterized complexity of bandwidth on trees. In International Colloquium on Automata, Languages, and Programming, pages 405-416, 2014. URL: https://doi.org/10.1007/978-3-662-43948-7_34.
  14. Zdeněk Dvořák and Sergey Norin. Treewidth of graphs with balanced separations. Journal of Combinatorial Theory, Series B, 137:137-144, 2019. URL: https://doi.org/10.1016/j.jctb.2018.12.007.
  15. Martina Eikel, Christian Scheideler, and Alexander Setzer. Minimum linear arrangement of series-parallel graphs. In Proc. of the 12th International Workshop on Approximation and Online Algorithms, pages 168-180. Springer, 2014. URL: https://doi.org/10.1007/978-3-319-18263-6_15.
  16. Shimon Even and Yossi Shiloach. NP-completeness of several arrangement problems. Technical report 43, Dept. Computer Science, Technicon, Haifa, Isreal, 1975. Google Scholar
  17. Uriel Feige. Approximating the bandwidth via volume respecting embeddings. J. Comput. Syst. Sci., 60(3):510-539, 2000. URL: https://doi.org/10.1006/jcss.1999.1682.
  18. 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.
  19. Uriel Feige and James R. Lee. An improved approximation ratio for the minimum linear arrangement problem. Inf. Process. Lett., 101(1):26-29, 2007. URL: https://doi.org/10.1016/j.ipl.2006.07.009.
  20. Uriel Feige and Kunal Talwar. Approximating the bandwidth of caterpillars. Algorithmica, 55(1):190-204, 2009. URL: https://doi.org/10.1007/s00453-007-9002-0.
  21. Peter Fishburn, Prasad Tetali, and Peter Winkler. Optimal linear arrangement of a rectangular grid. Discrete Mathematics, 213(1-3):123-139, 2000. URL: https://doi.org/10.1016/S0012-365X(99)00173-9.
  22. M. R. Garey, David S. Johnson, and Larry J. Stockmeyer. Some simplified NP-complete graph problems. Theor. Comput. Sci., 1(3):237-267, 1976. URL: https://doi.org/10.1016/0304-3975(76)90059-1.
  23. Michael R. Garey and David S. Johnson. Computers and Intractability: A Guide to the Theory of NP-Completeness. W. H. Freeman & Co., 1979. Google Scholar
  24. MK Goldberg and IA Klipker. Minimal placing of trees on a line. In Physico-Technical Institute of Low Temperatures. Academy of Sciences of Ukranian SSR, 1976. Google Scholar
  25. Anupam Gupta. Improved bandwidth approximation for trees and chordal graphs. J. Algorithms, 40(1):24-36, 2001. URL: https://doi.org/10.1006/jagm.2000.1118.
  26. Lawrence Hueston Harper. Optimal assignments of numbers to vertices. Journal of the Society for Industrial and Applied Mathematics, 12(1):131-135, 1964. URL: https://doi.org/10.1137/0112012.
  27. Michael Held and Richard M. Karp. The traveling-salesman problem and minimum spanning trees. Oper. Res., 18(6):1138-1162, 1970. URL: https://doi.org/10.1287/opre.18.6.1138.
  28. Martin Juvan and Bojan Mohar. Optimal linear labelings and eigenvalues of graphs. Discrete Applied Mathematics, 36(2):153-168, 1992. URL: https://doi.org/10.1016/0166-218X(92)90229-4.
  29. T. Kloks. Treewidth: Computations and Approximations. Springer-Verlag New York, 1994. Google Scholar
  30. Yehuda Koren and David Harel. A multi-scale algorithm for the linear arrangement problem. In International Workshop on Graph-Theoretic Concepts in Computer Science, pages 296-309. Springer, 2002. URL: https://doi.org/10.1007/3-540-36379-3_26.
  31. Joel Mackenzie, Antonio Mallia, Matthias Petri, J. Shane Culpepper, and Torsten Suel. Compressing inverted indexes with recursive graph bisection: A reproducibility study. In Advances in Information Retrieval, pages 339-352, Cham, 2019. Springer International Publishing. URL: https://doi.org/10.1007/978-3-030-15712-8_22.
  32. Silviu Maniu, Pierre Senellart, and Suraj Jog. An experimental study of the treewidth of real-world graph data. In Pablo Barceló and Marco Calautti, editors, Proc. of the 22nd International Conference on Database Theory, volume 127, pages 12:1-12:18, 2019. URL: https://doi.org/10.4230/LIPIcs.ICDT.2019.12.
  33. Julián Mestre, Sergey Pupyrev, and Seeun William Umboh. On the Extended TSP problem. In Proc. of the 32nd International Symposium on Algorithms and Computation, volume 212, pages 42:1-42:14, 2021. URL: https://doi.org/10.4230/LIPIcs.ISAAC.2021.42.
  34. Christos H. Papadimitriou and Mihalis Yannakakis. The traveling salesman problem with distances one and two. Math. Oper. Res., 18(1):1-11, 1993. URL: https://doi.org/10.1287/moor.18.1.1.
  35. Satish Rao and Andréa W. Richa. New approximation techniques for some linear ordering problems. SIAM Journal on Computing, 34(2):388-404, 2005. URL: https://doi.org/10.1137/S0097539702413197.
  36. Neil Robertson and Paul D Seymour. Graph minors. V. Excluding a planar graph. Journal of Combinatorial Theory, Series B, 41(1):92-114, 1986. URL: https://doi.org/10.1016/0095-8956(86)90030-4.
  37. James B Saxe. Dynamic-programming algorithms for recognizing small-bandwidth graphs in polynomial time. SIAM Journal on Algebraic Discrete Methods, 1(4):363-369, 1980. URL: https://doi.org/10.1137/0601042.
  38. Wikipedia contributors. Hilbert curve. URL: https://en.wikipedia.org/wiki/Hilbert_curve.
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