DFG Project Report: Space-efficient Algorithms

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. [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.

Graphen kommen in vielen Anwendungen vor, von sozialen Netzwerken bis hin zu Transport und Logistik. Häufig werden diese Graphen aus riesigen Datensätzen erstellt, die als Big Data bezeichnet werden. Da die Anwendungen mit immer größeren Datenmengen konfrontiert werden, wurden Lösungen aus verschiedensten Richtungen entwickelt. Eine dieser Forschungsrichtungen sind die so genannten platzeffizienten Algorithmen, die für ein bestimmtes Problem darauf abzielen, die Laufzeit von Standardlösungen beizubehalten und gleichzeitig den Speicherbedarf erheblich zu reduzieren, was in der Regel bedeutet, dass eine lineare Anzahl von Bits verwendet wird. Dies wird durch die Beobachtung motiviert, dass Algorithmen, die eine sublineare Menge an Speicherplatz verwenden, zu enormen Laufzeiten tendieren, zusammen mit einer unteren Schranke von Barnes et al. [SIAM J. Comput., 1998], dass gerichtete s-t-Konnektivität in bestimmten Modellen nicht in polynomieller Zeit mit o(n/√ log n) Bits gelöst werden kann. Vor dem Forschungsprojekt waren nur wenige platzeeffiziente Algorithmen bekannt, zum Beispiel für platzeffiziente Varianten von Tiefen- und Breitensuche. Diese genannten platzeffizienten Algorithmen verwenden eine lineare Anzahl von Bits, während sie die optimale lineare Laufzeit (fast) beibehalten. Das Projekt hat die Toolbox für platzeffiziente Algorithmen um mächtige Frameworks erweitert, wie zum Beispiel Algorithmen für die Konstruktion so genannter Baumzerlegungen, eine Struktur, die häufig beim Entwurf parametrisierter Algorithmen für NP-schwere Probleme verwendet wird. Andere Ergebnisse umfassen Algorithmen für spezielle Klassen von Graphen wie planare Graphen und Graphen, die durch sogenannte verbotene Minoren kategorisiert werden können. Ein solches Ergebnis ist ein sogenanntes Graph-Coarsening-Framework, das es ermöglicht, verschiedene Algorithmen platzeffizient auszuführen, mit einem leichten Verlust in der Lösungsqualität. Die Ergebnisse des Projekts umfassen nicht nur statische Graphen, sondern auch dynamische. Erstens für die Konstruktion effizienter und succincter Datenstrukturen, die sogenannte Minor-Operationen (Knotenlöschung sowie das Löschen/Zusammenziehen von Kanten) in planaren Graphen bereitstellen. Minor-Operationen sind in zahlreichen Anwendungen nützlich. Mit Hilfe des oben erwähnten Graph-Coarsening Frameworks kann die genannte Datenstruktur platzeffizient konstruiert werden. Zweitens, platzeffiziente Ergebnisse für sogenannte Explorations- und Multi-Stage-Probleme auf temporalen Graphen, das heißt auf Graphen bei denen sich die Menge der Kanten über diskrete Zeitschritte ändert. Für praktische Anwendungen wurden mit Hilfe von platzeffizienten Strategien ein erfolgreicher Solver für die PACE-Challenge 2024 entworfen, der eine obere Schranke für den Parameter der so genannten Twinwidth berechnet, sowie verschiedene platzeffiziente Algorithmen und Datenstrukturen in einer Bibliothek implementiert.