Space-Efficient Graph-Algorithms 2
Final Report Abstract
Graphs arise in many applications, from social networks to transportation and logistics. Often, these graphs are constructed from massive data sets, commonly referred to as Big Data. As applications are faced with ever-increasing amounts of data, researchers tackled the problem from various directions. One such direction is the field of so-called space-efficient algorithms, which for a given problem aim to maintain the runtime of standard solutions while significantly reducing the memory requirements, which typically means using a linear number of bits. This is motivated by the observation that algorithms using a sublinear amount of space tend to have impractical runtimes, together with a lower bound of Barnes et al. [1998], who showed that directed s-t-connectivity can not be solved in polynomial time with o(n/ √log n) bits in certain models. Prior to the research project, only a handful of space-efficient algorithms were known such as those for standard graph traversals like depth-first search and breadth-first search. These algorithms use a linear number of bits while (almost) maintaining an optimal linear runtime. We have extended the toolbox of space-efficient algorithms with powerful frameworks such as algorithms for constructing so-called tree decompositions, a structure commonly used in the design of parameterized algorithms for NP-hard problems. Other results include algorithms for special classes of graphs such as planar graphs and graphs that can be categorized by so-called forbidden minors. One such result is a so-called graph-coarsening framework that allows us to execute various algorithms space-efficiently with a trade-off in solution quality. We have obtained results not only for static graphs, but also in the dynamic settings. First, for the construction of efficient and succinct data structures that provides so-called minor operations (delete vertices as well as delete/contract edges) in planar graphs. Minor operations are useful in numerous applications. Using the aforementioned graph-coarsening framework we are able to construct this data structure space-efficiently. Second, space-efficient results for so-called exploration and multi-stage problems on temporal graphs, i.e., graphs where the set of edges changes over discrete time steps. For practical applications, we applied our knowledge of space-efficient techniques to design a winning solver for the PACE challenge 2024 on upper bounding the parameter of so-called twinwidth, in addition to implementing various space-efficient algorithms and data structures in a library.
Link to the final report
https://doi.org/10.34657/17574
Publications
-
Extra space during initialization of succinct data structures and dynamical initializable arrays. In Proc. 43rd International Symposium on Mathematical Foundations of Computer Science (MFCS 2018), volume 117 of LIPIcs, pages 65:1–65:16. Schloss Dagstuhl – Leibniz-Zentrum für Informatik.
Frank Kammer & Andrej Sajenko
-
Simple 2f -color choice dictionaries. In Proc. 29th International Symposium on Algorithms and Computation (ISAAC 2018), volume 123 of LIPIcs, pages 66:1–66:12. Schloss Dagstuhl – Leibniz-Zentrum für Informatik.
Frank Kammer & Andrej Sajenko
-
Space efficient (graph) algorithms. 2018
Frank Kammer & Andrej Sajenko
-
Linear-Time In-Place DFS and BFS on the Word RAM. Lecture Notes in Computer Science, 286-298. Springer International Publishing.
Kammer, Frank & Sajenko, Andrej
-
Two moves per time step make a difference. In Proc. 46th International Colloquium on Automata, Languages, and Programming (ICALP 2019), volume 132 of LIPIcs, pages 141:1–141:14.
Thomas Erlebach, Frank Kammer, Kelin Luo, Andrej Sajenko & Jakob T. Spooner
-
Multistage graph problems on a global budget. Theoretical Computer Science, 868, 46-64.
Heeger, Klaus; Himmel, Anne-Sophie; Kammer, Frank; Niedermeier, Rolf; Renken, Malte & Sajenko, Andrej
-
Space-efficient graph coarsening with applications to succinct planar encodings. In Proc. 33rd International Symposium on Algorithms and Computation (ISAAC 2022), volume 248 of LIPIcs, pages 62:1–62:15. Schloss Dagstuhl – Leibniz-Zentrum für Informatik.
Frank Kammer & Johannes Meintrup
-
Space-Efficient Vertex Separators for Treewidth. Algorithmica, 84(9), 2414-2461.
Kammer, Frank; Meintrup, Johannes & Sajenko, Andrej
-
Open problems in (hyper)graph decomposition, 2023
Deepak Ajwani, Rob H. Bisseling, Katrin Casel, Ümit V. Çatalyürek, Cédric Chevalier, Florian Chudigiewitsch, Marcelo Fonseca Faraj, Michael Fellows, Lars Gottesbüren, Tobias Heuer, George Karypis, Kamer Kaya, Jakub Lacki, Johannes Langguth, Xiaoye Sherry Li, Ruben Mayer, Johannes Meintrup, Yosuke Mizutani ... & Albert-Jan Yzelman
-
Pace solver description: Exact (guthmi) and heuristic (guthm). In Proc. 18th International Symposium on Parameterized and Exact Computation (IPEC 2023), volume 285 of LIPIcs, pages 37:1–37:7. Schloss Dagstuhl – Leibniz-Zentrum für Informatik
Alexander Leonhardt, Holger Dell, Anselm Haak, Frank Kammer, Johannes Meintrup, Ulrich Meyer & Manuel Penschuck
-
Recent trends in graph decomposition (dagstuhl seminar 23331). Dagstuhl Reports, 13(8):1–45
George Karypis, Christian Schulz, Darren Strash, Deepak Ajwani, Rob H. Bisseling, Katrin Casel, Ümit V. Çatalyürek, Cédric Chevalier, Florian Chudigiewitsch, Marcelo Fonseca Faraj, Michael R. Fellows, Lars Gottesbüren, Tobias Heuer, Kamer Kaya, Jakub Lacki, Johannes Langguth, Xiaoye Sherry Li, Ruben Mayer ... & Albert-Jan Yzelman
-
Sorting and Ranking of Self-Delimiting Numbers with Applications to Tree Isomorphism. Lecture Notes in Computer Science, 356-367. Springer Nature Switzerland.
Kammer, Frank; Meintrup, Johannes & Sajenko, Andrej
-
Star: Library for space- and timeefficient algorithms. 2023
Nina Hammer, Frank Kammer & Johannes Meintrup
-
Succinct planar encoding with minor operations. In Proc. 34th International Symposium on Algorithms and Computation (ISAAC 2023), volume 283 of LIPIcs, pages 44:1–44:18. Schloss Dagstuhl – Leibniz-Zentrum für Informatik.
Frank Kammer & Johannes Meintrup
-
Exploiting automorphisms of temporal graphs for fast exploration and rendezvous. In Proc. 51st International Colloquium on Automata, Languages, and Programming, (ICALP 2024), volume 297 of LIPIcs, pages 55:1–55:18. Schloss Dagstuhl – Leibniz-Zentrum für Informatik, 2024.
Konstantinos Dogeas, Thomas Erlebach, Frank Kammer, Johannes Meintrup & William K. Moses Jr.
-
Space-Efficient Graph Kernelizations. Lecture Notes in Computer Science, 260-271. Springer Nature Singapore.
Kammer, Frank & Sajenko, Andrej
