On Hard Subgraph Problems: Parameterized Algorithms and Efficient Implementations

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