Treffer: On Hard Subgraph Problems: Parameterized Algorithms and Efficient Implementations ; Über Schwere Teilgraphprobleme: Parametrisierte Algorithmen und Effiziente Implementierungen

We study various subgraph problems with applications for example in community detection. In these applications vertices represent agents in a social network or genes in a biological network, and edges represent interactions of the agents or genes, respectively. All of the problems studied in this thesis fit into one of two categories: finding one subgraph fulfilling some specific property, or enumerating all subgraphs of a certain type. We study these problems both theoretically, for example with respect to their classic- and parameterized complexity, and practically, by providing efficient implementations. We study three types of problems: In many applications like the detection of network motifs, it is important to enumerate all connected induced subgraphs. We compare several implementations for this task and improve upon the best delay due to Elbassioni (JGAA '15). Then, we use the fastest algorithms for this task as a baseline for an exact solver for Connected Fixed Cardinality Optimization. In this problem, one aims to find a set of k vertices maximizing an objective function. We provide several generic pruning rules to speed-up our solver and show for eight example problems that our approach outperforms standard Integer Linear Programs (ILPs) for small values of k. Community detection is an important task in the analysis of networks. Clique relaxations are a popular tool to model communities. We study the parameterized complexity of finding or enumerating different clique relaxations with respect to the (weak) closure. These parameters were recently discovered by Fox et al. (SIAM J. Comput. '20) and are observed to be small in social networks. Then, we study the diameter-based clique relaxation 2-Club with triangle or seed constraints. For the variants with triangle constraints we provide a dichotomy into cases which admit an FPT-algorithm and those which are W[1]-hard for k. Next, we provide a branch-and-bound algorithm which outperforms an ILP by Almeida and Brás (Comput. Oper. Res. '19). For the seeded ...