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

Full description

Saved in:
Bibliographic Details
Main Author: Sommer, Frank
Contributors: Komusiewicz, Christian (Prof. Dr.) (Thesis advisor)
Format: Doctoral Thesis
Language:English
Published: Philipps-Universität Marburg 2022
Subjects:
Online Access:PDF Full Text
Tags: Add Tag
No Tags, Be the first to tag this record!

Wir untersuchen verschiedene Subgraphprobleme mit Anwendungen etwa im Finden von Communities. In diesen Anwendungen repräsentieren Knoten Akteure in sozialen Netzwerken oder Gene in einem biologischem Netzwerk und Kanten repräsentieren Interaktionen der Akteure beziehungsweise der Gene. Alle Probleme, welche in dieser Dissertation untersucht werden, gehören zu zwei Kategorien: finden eines Subgraphen, welcher eine bestimmte Eigenschaft erfüllt, oder Aufzählen aller Subgraphen eines bestimmten Typs. Wir untersuchen diese Probleme sowohl theoretisch, zum Beispiel bezüglich deren klassischer oder parametrisierten Komplexität, als auch praktisch, indem wir effiziente Implementierungen entwickeln. In vielen Anwendungen, wie zum Beispiel dem Finden von Netzwerkmotiven, ist es wichtig alle zusammenhängenden induzierten Subgraphen aufzuzählen. Wir vergleichen verschiedene Implementierungen für diese Aufgabe und verbessern den besten Delay für dieses Problem, welcher von Elbassioni (JGAA '15) nachgewisen wurde. Danach nutzen wir die schnellsten Algorithmen für diese Aufgabe als Grundlage für einen exakten Solver für Connected Fixed Cardinality Optimization. In diesem Problem möchte man eine Menge von k Knoten finden, welche eine Zielfunktion maximiert. Wir stellen viele generische Pruningregeln zur Beschleunigung unseres Solvers zur Verfügung und zeigen für acht Beispielprobleme, dass unser Ansatz für kleine Werte von k schneller ist als Standardformulierungen von Ganzzahligen Linearen Programmen (ILPs). Das Finden von Communities ist eine wichtige Aufgabe in der Analyse von Netzwerken. Cliquerelaxierungen sind ein weit verbreiteter Ansatz um Communities zu modellieren. Wir untersuchen die parametrisierte Komplexität bezüglich der (weak) closure, um verschiedene Cliquerelaxierungen zu finden oder aufzuzählen. Diese Parameter wurden kürzlich von Fox et al. (SIAM J. Comput. '20) entdeckt und sind klein in sozialen Netzwerken. Danach untersuchen wir die durchmesserbasierte Cliquerelaxierung 2-Club mit Dreiecks- oder Seedconstraint. Für die Varianten mit Dreiecksconstraints beweisen wir eine Dichotomie in Fälle, welche einen FPT-Algorithmus für k zulassen, und solche, welche W[1]-schwer für k sind. Außerdem entwickeln wir einen Branch-and-Bound Algorithmus, welcher schneller ist als ein ILP von Almeida and Brás (Comput. Oper. Res. 2019). Für die Variante mit Seedconstraint finden wir viele Fälle, welche einen FPT-Algorithmus für k zulassen und solche, welche W[1]-schwer für k sind. Diese Klassifikation hängt von der Struktur des Seeds ab. Schließlich untersuchen wir ein lokales Graphpartitionierungsproblem, welches viele klassische Graphprobleme wie Densest k-Subgraph, Maximum Partial Vertex Cover (MaxPVC) und Maximum (k,n-k)-Cut verallgemeinert. Wir untersuchen die parametrisierte Komplexität von diesem generischen Graphproblem bezüglich der Lösungsgröße k sowie einem zusätzlichen strukturellen Graphparameter wie dem Maximalgrad oder der c-Closure. Zum Beispiel zeigen wir, dass sich MaxPVC und Maximum (k,n-k)-Cut nicht nur gleich verhalten im Sinne von FPT-Algorithmen, sondern auch die Techniken, um diese Ergebnisse zu erzielen, identisch sind. Eines unserer Ergebnisse ist ein sogenannter Kern der Größe k^(O(c)) für MaxPVC. Dieses Resultat beantwortet eine offene Frage von Kanesh et al. (STACS '22).