2025, Kammer, Frank

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. [SIAM J. Comput., 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.