Document Open Access Logo

On Dynamic α + 1 Arboricity Decomposition and Out-Orientation

Authors Aleksander B. G. Christiansen, Jacob Holm, Eva Rotenberg , Carsten Thomassen

PDF
Thumbnail PDF

File

LIPIcs.MFCS.2022.34.pdf
  • Filesize: 0.93 MB
  • 15 pages

Document Identifiers

Author Details

Aleksander B. G. Christiansen
  • Department of Applied Mathematics and Computer Science, Technical University of Denmark, Denmark
Jacob Holm
  • Department of Computer Science, University of Copenhagen, Copenhagen, Denmark
Eva Rotenberg
  • Department of Applied Mathematics and Computer Science, Technical University of Denmark, Denmark
Carsten Thomassen
  • Department of Applied Mathematics and Computer Science, Technical University of Denmark, Denmark

Funding

  • Christiansen, Aleksander B. G.: Partially supported by the VILLUM Foundation grant 37507 "Efficient Recomputations for Changeful Problems".
  • Holm, Jacob: Partially supported by the VILLUM Foundation grant 16582, "BARC"
  • Rotenberg, Eva: Partially supported by Independent Research Fund Denmark grants 2020-2023 (9131-00044B) "Dynamic Network Analysis" and 2018-2023 (8021-00249B) "AlgoGraph", and the VILLUM Foundation grant 37507 "Efficient Recomputations for Changeful Problems".
  • Thomassen, Carsten: Partially supported by Independent Research Fund Denmark grant 2018-2023 (8021-00249B) "AlgoGraph".

Acknowledgements

We thank Irene Parada for helpful discussions.

Cite As Get BibTex

Aleksander B. G. Christiansen, Jacob Holm, Eva Rotenberg, and Carsten Thomassen. On Dynamic α + 1 Arboricity Decomposition and Out-Orientation. In 47th International Symposium on Mathematical Foundations of Computer Science (MFCS 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 241, pp. 34:1-34:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022) https://doi.org/10.4230/LIPIcs.MFCS.2022.34

Abstract

A graph has arboricity α if its edges can be partitioned into α forests. The dynamic arboricity decomposition problem is to update a partitioning of the graph’s edges into forests, as a graph undergoes insertions and deletions of edges. We present an algorithm for maintaining partitioning into α+1 forests, provided the arboricity of the dynamic graph never exceeds α. Our algorithm has an update time of Õ(n^{3/4}) when α is at most polylogarithmic in n.
Similarly, the dynamic bounded out-orientation problem is to orient the edges of the graph such that the out-degree of each vertex is at all times bounded. For this problem, we give an algorithm that orients the edges such that the out-degree is at all times bounded by α+1, with an update time of Õ(n^{5/7}), when α is at most polylogarithmic in n. Here, the choice of α+1 should be viewed in the light of the well-known lower bound by Brodal and Fagerberg which establishes that, for general graphs, maintaining only α out-edges would require linear update time.
However, the lower bound by Brodal and Fagerberg is non-planar. In this paper, we give a lower bound showing that even for planar graphs, linear update time is needed in order to maintain an explicit three-out-orientation. For planar graphs, we show that the dynamic four forest decomposition and four-out-orientations, can be updated in Õ(n^{1/2}) time.

Subject Classification

ACM Subject Classification
  • Theory of computation → Dynamic graph algorithms
Keywords
  • Dynamic graphs
  • bounded arboricity
  • data structures

Metrics

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

References

  1. Oswin Aichholzer, Franz Aurenhammer, and Günter Rote. Optimal graph orientation with storage applications. SFB-Report , SFB 'Optimierung und Kontrolle'. TU Graz, 1995. Reportnr.: F003-51. Google Scholar
  2. Stephen Alstrup, Jacob Holm, Kristian De Lichtenberg, and Mikkel Thorup. Maintaining information in fully dynamic trees with top trees. ACM Trans. Algorithms, 1(2):243-264, October 2005. URL: https://doi.org/10.1145/1103963.1103966.
  3. Srinivasa Rao Arikati, Anil Maheshwari, and Christos D. Zaroliagis. Efficient computation of implicit representations of sparse graphs. Discret. Appl. Math., 78(1-3):1-16, 1997. URL: https://doi.org/10.1016/S0166-218X(97)00007-3.
  4. Niranka Banerjee, Venkatesh Raman, and Saket Saurabh. Fully dynamic arboricity maintenance. In Computing and Combinatorics - 25th International Conference, COCOON 2019, Xi'an, China, July 29-31, 2019, Proceedings, volume 11653 of Lecture Notes in Computer Science, pages 1-12. Springer, 2019. URL: https://doi.org/10.1007/978-3-030-26176-4_1.
  5. Edvin Berglin and Gerth Stolting Brodal. A Simple Greedy Algorithm for Dynamic Graph Orientation. In 28th International Symposium on Algorithms and Computation (ISAAC 2017), volume 92 of Leibniz International Proceedings in Informatics (LIPIcs), pages 12:1-12:12, Dagstuhl, Germany, 2017. Schloss Dagstuhl-Leibniz-Zentrum fuer Informatik. URL: https://doi.org/10.4230/LIPIcs.ISAAC.2017.12.
  6. Markus Blumenstock. Fast algorithms for pseudoarboricity. In Proceedings of the Eighteenth Workshop on Algorithm Engineering and Experiments, ALENEX 2016, Arlington, Virginia, USA, January 10, 2016, pages 113-126. SIAM, 2016. URL: https://doi.org/10.1137/1.9781611974317.10.
  7. Markus Blumenstock and Frank Fischer. A constructive arboricity approximation scheme. In SOFSEM 2020: Theory and Practice of Computer Science - 46th International Conference on Current Trends in Theory and Practice of Informatics, SOFSEM 2020, Limassol, Cyprus, January 20-24, 2020, Proceedings, volume 12011 of Lecture Notes in Computer Science, pages 51-63. Springer, 2020. URL: https://doi.org/10.1007/978-3-030-38919-2_5.
  8. Enno Brehm. 3-orientations and schnyder 3-tree-decompositions, 2000. Google Scholar
  9. Gerth Stolting Brodal and Rolf Fagerberg. Dynamic representations of sparse graphs. In In Proc. 6th International Workshop on Algorithms and Data Structures (WADS), pages 342-351. Springer-Verlag, 1999. Google Scholar
  10. Aleksander B. G. Christiansen. Dynamic algorithms for implicit vertex-colouring of graphs with bounded arboricity. Master’s thesis, Technical University of Denmark, Kgs. Lyngby, Denmark, October 2021. Google Scholar
  11. Aleksander B. G. Christiansen and Eva Rotenberg. Fully-dynamic α + 2 arboricity decompositions and implicit colouring. In ICALP, volume 229 of LIPIcs, pages 42:1-42:20. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2022. Google Scholar
  12. Marek Chrobak and David Eppstein. Planar orientations with low out-degree and compaction of adjacency matrices. Theor. Comput. Sci., 86(2):243-266, 1991. Google Scholar
  13. Giuseppe Di Battista and Roberto Tamassia. Incremental planarity testing (extended abstract). In 30th Annual Symposium on Foundations of Computer Science, Research Triangle Park, North Carolina, USA, 30 October - 1 November 1989, pages 436-441, 1989. URL: https://doi.org/10.1109/SFCS.1989.63515.
  14. Jack Edmonds. Minimum partition of a matroid into independent subsets. Journal of Research of the National Bureau of Standards Section B Mathematics and Mathematical Physics, page 67, 1965. Google Scholar
  15. David Eppstein. Arboricity and bipartite subgraph listing algorithms. Inf. Process. Lett., 51(4):207-211, August 1994. URL: https://doi.org/10.1016/0020-0190(94)90121-X.
  16. David Eppstein. Dynamic generators of topologically embedded graphs. In Proceedings of the Fourteenth Annual ACM-SIAM Symposium on Discrete Algorithms, January 12-14, 2003, Baltimore, Maryland, USA., pages 599-608, 2003. URL: http://dl.acm.org/citation.cfm?id=644108.644208.
  17. David Eppstein, Zvi Galil, Giuseppe F. Italiano, and Thomas H. Spencer. Separator based sparsification: I. planarity testing and minimum spanning trees. Journal of Computer and Systems Sciences, 52(1):3-27, February 1996. URL: https://doi.org/10.1006/jcss.1996.0002.
  18. Harold Gabow and Herbert Westermann. Forests, frames, and games: Algorithms for matroid sums and applications. In Proceedings of the Twentieth Annual ACM Symposium on Theory of Computing, STOC '88, pages 407-421, New York, NY, USA, 1988. Association for Computing Machinery. Google Scholar
  19. Harold N. Gabow. Algorithms for graphic polymatroids and parametric s-sets. In Proceedings of the Sixth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA '95, pages 88-97, USA, 1995. Society for Industrial and Applied Mathematics. Google Scholar
  20. Zvi Galil, Giuseppe F. Italiano, and Neil Sarnak. Fully dynamic planarity testing with applications. Journal of the ACM, 46(1):28-91, 1999. URL: https://doi.org/10.1145/300515.300517.
  21. David G. Harris, Hsin-Hao Su, and Hoa T. Vu. On the locality of nash-williams forest decomposition and star-forest decomposition. In Avery Miller, Keren Censor-Hillel, and Janne H. Korhonen, editors, PODC '21: ACM Symposium on Principles of Distributed Computing, Virtual Event, Italy, July 26-30, 2021, pages 295-305. ACM, 2021. URL: https://doi.org/10.1145/3465084.3467908.
  22. Meng He, Ganggui Tang, and N. Zeh. Orienting dynamic graphs, with applications to maximal matchings and adjacency queries. In ISAAC, 2014. Google Scholar
  23. Monika Henzinger, Stefan Neumann, and Andreas Wiese. Explicit and implicit dynamic coloring of graphs with bounded arboricity. CoRR, abs/2002.10142, 2020. URL: http://arxiv.org/abs/2002.10142.
  24. Jacob Holm and Eva Rotenberg. Fully-dynamic planarity testing in polylogarithmic time. In Proccedings of the 52nd Annual ACM SIGACT Symposium on Theory of Computing, STOC 2020, Chicago, IL, USA, June 22-26, 2020, pages 167-180. ACM, 2020. URL: https://doi.org/10.1145/3357713.3384249.
  25. Jacob Holm and Eva Rotenberg. Worst-case polylog incremental spqr-trees: Embeddings, planarity, and triconnectivity. In Shuchi Chawla, editor, Proceedings of the 2020 ACM-SIAM Symposium on Discrete Algorithms, SODA 2020, Salt Lake City, UT, USA, January 5-8, 2020, pages 2378-2397. SIAM, 2020. Full version: https://arxiv.org/abs/1910.09005. URL: https://doi.org/10.1137/1.9781611975994.146.
  26. Giuseppe F. Italiano, Johannes A. La Poutré, and Monika Rauch. Fully dynamic planarity testing in planar embedded graphs (extended abstract). In Algorithms - ESA '93, First Annual European Symposium, Bad Honnef, Germany, September 30 - October 2, 1993, Proceedings, pages 212-223, 1993. URL: https://doi.org/10.1007/3-540-57273-2_57.
  27. Tsvi Kopelowitz, Robert Krauthgamer, Ely Porat, and Shay Solomon. Orienting fully dynamic graphs with worst-case time bounds. In Automata, Languages, and Programming - 41st International Colloquium, ICALP 2014, Copenhagen, Denmark, July 8-11, 2014, Proceedings, Part II, volume 8573 of Lecture Notes in Computer Science, pages 532-543. Springer, 2014. URL: https://doi.org/10.1007/978-3-662-43951-7_45.
  28. Łukasz Kowalik. Approximation scheme for lowest outdegree orientation and graph density measures. In Proceedings of the 17th International Conference on Algorithms and Computation, ISAAC'06, pages 557-566, Berlin, Heidelberg, 2006. Springer-Verlag. URL: https://doi.org/10.1007/11940128_56.
  29. Łukasz Kowalik. Adjacency queries in dynamic sparse graphs. Inf. Process. Lett., 102(5):191-195, May 2007. URL: https://doi.org/10.1016/j.ipl.2006.12.006.
  30. Yin Tat Lee and Aaron Sidford. Path finding methods for linear programming: Solving linear programs in Õ(vrank) iterations and faster algorithms for maximum flow. In 2014 IEEE 55th Annual Symposium on Foundations of Computer Science, pages 424-433, 2014. URL: https://doi.org/10.1109/FOCS.2014.52.
  31. Aleksander Madry. Navigating central path with electrical flows: From flows to matchings, and back. In 2013 IEEE 54th Annual Symposium on Foundations of Computer Science, pages 253-262, 2013. URL: https://doi.org/10.1109/FOCS.2013.35.
  32. C. St.J. A. Nash-Williams. Edge-disjoint spanning trees of finite graphs. Journal of the London Mathematical Society, s1-36(1):445-450, 1961. URL: https://doi.org/10.1112/jlms/s1-36.1.445.
  33. C. St.J. A. Nash-Williams. Decomposition of finite graphs into forests. Journal of the London Mathematical Society, s1-39(1):12-12, 1964. URL: https://doi.org/10.1112/jlms/s1-39.1.12.
  34. Jean-Claude Picard and Maurice Queyranne. A network flow solution to some nonlinear 0-1 programming problems, with applications to graph theory. Networks, 12(2):141-159, 1982. URL: https://doi.org/10.1002/net.3230120206.
  35. Johannes A. La Poutré. Alpha-algorithms for incremental planarity testing (preliminary version). In Proceedings of the Twenty-Sixth Annual ACM Symposium on Theory of Computing, 23-25 May 1994, Montréal, Québec, Canada, pages 706-715, 1994. URL: https://doi.org/10.1145/195058.195439.
  36. Daniel D. Sleator and Robert Endre Tarjan. A data structure for dynamic trees. In Proceedings of the Thirteenth Annual ACM Symposium on Theory of Computing, STOC '81, pages 114-122, New York, NY, USA, 1981. Association for Computing Machinery. URL: https://doi.org/10.1145/800076.802464.
  37. Shay Solomon and Nicole Wein. Improved dynamic graph coloring. ACM Trans. Algorithms, 16(3), June 2020. URL: https://doi.org/10.1145/3392724.
  38. Jeffery Westbrook. Fast incremental planarity testing. In Automata, Languages and Programming, 19th International Colloquium, ICALP92, Vienna, Austria, July 13-17, 1992, Proceedings, pages 342-353, 1992. URL: https://doi.org/10.1007/3-540-55719-9_86.
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