Space-Efficient Graph-Algorithms 2

• Applicant: Professor Dr. Frank Kammer
• Subject Area: Theoretical Computer Science
• Term: since 2017
• Project identifier: Deutsche Forschungsgemeinschaft (DFG) - Project number 379157101

The objectives of the proposal are twofold. On the one side, our work focuses on new space-efficient parameterized and approximation algorithms to run on a CPU and with adaptations also on a GPU where space limitations are often a major problem (Rhu et al., MICRO 2016). Algorithms on a GPU or hybrid algorithms on both CPU and GPU are of special interest for artificial intelligence where, e.g., recent results show that parameterized algorithms can help to speedup the training in Bayesian networks (Scanagatta et al., NeurIPS 2016). On the other side, many problems in bioinformatics are solved on systems with 128GB or much more RAM by using tools based on (temporal-)graph algorithms---again, a major problem of the applications based on (temporal-)graph algorithms is the space required (Strasser et al., ESA 2020).In detail, a core area of our objectives is to make further FPT algorithms (with parameters, e.g., treedepth, cliquewidth, or outerplanarity index) as well as approximation algorithms (e.g., Baker's PTAS) space efficient. In contrast to previous research, we now also target on special graph classes (as planar, chordal, and unit-disk graphs), their recognition and special data structures for the graph classes (e.g., computing, storing, and accessing planar embeddings). A further research direction in this area is to reduce the space consumption of algorithms based on the so-called bidimensional theory. As a practical application, we want to find adaptions of our space-efficient algorithms to run on GPUs, which can improve solutions in artificial intelligence. Our adaptions can also be a help in recent approaches on graph neuronal networks (GNN) to solve combinatorial problems (Sato et al., NeurIPS 2019). A second core area of objectives targets are temporal graphs and their big-data applications as, e.g., road networks (Gendreau et al., Comput. Oper. Res. 2015) and bioinformatics where temporal graphs are used to reflect the similarity of biomolecules with changing connections over time (Han et al., Nature 2004). Many problems on a temporal graph can be solved by easy transformations to a "standard" graph. The focus on these transformations is usually only time efficiency. If n is the number of vertices and tau is the number of time steps of the temporal graph G, then the transformation usually introduces Theta(n tau) new vertices. Applying afterwards a (space-efficient) graph algorithm on the transformed graph usually means that we need Omega(n tau) bits. New approaches are necessary to find solutions with fewer space.

• DFG Programme: Research Grants