On Hard Subgraph Problems: Parameterized Algorithms and Efficient Implementations

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

Ausführliche Beschreibung

Gespeichert in:
Bibliographische Detailangaben
1. Verfasser: Sommer, Frank
Beteiligte: Komusiewicz, Christian (Prof. Dr.) (BetreuerIn (Doktorarbeit))
Format: Dissertation
Sprache:Englisch
Veröffentlicht: Philipps-Universität Marburg 2022
Schlagworte:
Online Zugang:PDF-Volltext
Tags: Tag hinzufügen
Keine Tags, Fügen Sie den ersten Tag hinzu!
Beschreibung
Zusammenfassung: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 variant, we identify several cases which admit an FPT-algorithm and cases which are W[1]-hard for k depending on the structure of the seed. Finally, we also investigate a local graph partitioning problem generalizing many classic graph problems like Densest k-Subgraph, Maximum Partial Vertex Cover (MaxPVC) and Maximum (k,n-k)-Cut. We study the parameterized complexity of this generic graph problem with respect to the solution size k plus one additional structural graph parameter like the maximum degree or the c-closure. We show, for example, that MaxPVC and Maximum (k,n-k)-Cut not only behave similarly in terms of fixed-parameter tractability, but also the techniques to obtain them are similar. One of our results is a so-called kernel of size k^(O(c)) for MaxPVC, thereby answering an open question of Kanesh et al. (STACS '22).
Umfang:301 Seiten
DOI:10.17192/z2023.0061